图论
Eva.Q Lv9
2021-08-24 09:55:46

跑图啰 ~ ~

开一个新 oj，叫 Eva.oj 专门存放 Co 老师给 Eva 口述的题 ~ ~

图是啥

图吧，由点和边组成，点可能有点权，边呢也可能会有边权，边还可分为 有向边（出边&入边）和 无向边 两种。

存图

矩阵（邻接矩阵）

矩阵 ， 则认为有 条从 号点到 号点的边。如果保证不重边则可认为 代表边权。（总而言之，就是， 刻画了这两个点之间的某种关系）

例1

Eva.oj 0001

Input Format

第一行两个整数 。代表这个图有 个点， 条边。接下来 行，每行三个整数 代表有一条边从 指向 ，且该边的边权为 。

Output Format

对于每个点，第一行输出该点共有几条出边，接下来对应输出，每条边指向的点和该边的边权。

解1

a[N][N] 存图，cnt[i] 存 号点的出边数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
#define N 1007
using namespace std;

int a[N][N];
int cnt[N];
int main(){
	int m, n;
	cin >> n >> m;
	for(int i = 1; i <= m; ++i){
		int u, v, w;
		cin >> u >> v >> w;
		a[u][v] = w;
		cnt[u]++;
	}
	for(int i = 1; i <= n; ++i){
		cout << cnt[i] << endl;
		for(int j = 1; j <= n; ++j){
			if(a[i][j]) cout << j << ' ' << a[i][j] << endl;
		}
	}
		
	return 0;
}
邻接表

如果一个图，有很多点，但边的数量却很少，如果用邻接矩阵存储，会浪费很多的资源，因此，我们选用邻接表的方式存储，有利于节省不必要的空间。

例1

Eva.oj 0002

在 Eva.oj 0001 的基础上除去边权，即该图的边，无边权。

解1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#define N 100007
using namespace std;

vector<int> a[N];

int main(){
	int m, n;
	cin >> n >> m;
	for(int i = 1; i <= m; ++i){
		int u, v;
		cin >> u >> v;
		a[u].push_back(v);
	}
	for(int i = 1; i <= n; ++i){
		cout << a[i].size() << endl;
		for(auto j : a[i]){
			cout << j << endl;
		}
	}
	return 0;
}
例2

Eva.oj 0001

Input Format

第一行两个整数 。代表这个图有 个点， 条边。接下来 行，每行三个整数 代表有一条边从 指向 ，且该边的边权为 。

Output Format

对于每个点，第一行输出该点共有几条出边，接下来对应输出，每条边指向的点和该边的边权。


现在又有边权啦，Eva 不会 pair ，所以写了结构体

解2-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
#define N 100007
using namespace std;

struct node{
	int v, w;
};

vector<node> a[N];

int main(){
	int m, n;
	cin >> n >> m;
	for(int i = 1; i <= m; ++i){
		int u, v, w;
		cin >> u >> v >> w;
		a[u].push_back((node){v, w});
	}
	for(int i = 1; i <= n; ++i){
		cout << a[i].size() << endl;
		for(auto j : a[i]){
			cout << j.v << ' ' << j.w << endl;
		}
	}
	return 0;
}
解2-2

Co老师教Eva用 pair

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
#define N 100007
using namespace std;


vector<pair<int, int> > a[N];

int main(){
	int m, n;
	cin >> n >> m;
	for(int i = 1; i <= m; ++i){
		int u, v, w;
		cin >> u >> v >> w;
		a[u].push_back(make_pair(v, w));
	}
	for(int i = 1; i <= n; ++i){
		cout << a[i].size() << endl;
		for(auto j : a[i]){
			cout << j.first << ' ' << j.second << endl;
		}
	}
	return 0;
}
链式前向星

“星”即指针，可此指针非彼指针。先上代码吧 ~

例1

Eva.oj 0001

Input Format

第一行两个整数 。代表这个图有 个点， 条边。接下来 行，每行三个整数 代表有一条边从 指向 ，且该边的边权为 。

Output Format

对于每个点，第一行输出该点共有几条出边，接下来对应输出，每条边指向的点和该边的边权。

解1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
#define N 100007
#define M 10000007
using namespace std;

struct node{
	int v, w, nxt;
}e[M], hd[N];

int tot;

inline void add(int u, int v, int w) {
	++tot;
	e[tot].v = v; e[tot].w = w;
	e[tot].nxt = hd[u].nxt;
	hd[u].nxt = tot; ++hd[u].w;
}

int main(){
	int m, n;
	cin >> n >> m;
	for(int i = 1; i <= m; ++i){
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
	}
	for(int i = 1; i <= n; ++i){
		cout << hd[i].w << endl;
		for(int j = hd[i].nxt; j; j = e[j].nxt ){
			cout << e[j].v << ' ' << e[j].w << endl;
		}
	}
	return 0;
}

hd[N] 就是 号点到 号点的头，可以开成一个 int 数组，也可以开成 node 用 node 里的 ，来存储该点有几条出边。接下来要在这些头的后面，接上它的出边（一条边有边权，起点和指向的点三个信息，所以我们用一个结构体来存储这些信息）。

e[M] 预留出 大小的空间，给每一条边。e[i] 中 就是每条边的编号。

遍历图

DFS

深度优先搜索 —— ”一条路走到黑，走不动了退一步“

例1

Eva.oj 0003

给一个无向图，输出连通块的数量。

Input Format

第一行两个整数 。代表这个图有 个点， 条边。接下来 行，每行两个整数 代表有一条边连接 和 。

Output Format

一个整数代表连通块的数量。

解1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
#define N 100007
using namespace std;

vector<int> a[N];
int vis[N];

inline int dfs(int x){
	vis[x] = 1;
	for(auto j : a[x])
		if(!vis[j]) dfs(j);
}

int main(){
	int m, n;
	cin >> n >> m;
	for(int i = 1; i <= m; ++i){
		int u, v;
		cin >> u >> v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	int cnt = 0;
	for(int i = 1; i <= n; ++i){
		if(!vis[i]) {dfs(i);cnt++;}
	}
	cout << cnt;
	return 0;
}
例2

Eva.oj 0004

给一个 个点的无向图，输出连通块数，接下来 行，输出各个连通块所含点的数量，且按从小到大的顺序输出该连通块中点的编号。

Input Format

第一行两个整数 。代表这个图有 个点， 条边。接下来 行，每行两个整数 代表有一条边连接 和 。

Output Format

第一行输出连通块数。接下来 行，每行若干个数字。第一个数字，代表连通块所含点的数量，后面按从小到的顺序，输出该连通块中点的编号。

解2

num 即为连通块的编号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
#define N 100007
using namespace std;

int vis[N];

vector<int> a[N], s[N];

inline int dfs(int x, int num){
	vis[x] = num;
	s[num].push_back(x);
	for(auto j : a[x])
		if(!vis[j]) dfs(j, num);
}

int main(){
	int m, n;
	cin >> n >> m;
	for(int i = 1; i <= m; ++i){
		int u, v;
		cin >> u >> v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	int cnt = 0;
	for(int i = 1; i <= n; ++i){
		if(!vis[i]) {dfs(i, ++cnt);}
	}
	cout << cnt << endl;
    
	for(int i = 1; i <= cnt; ++i){
		sort(s[i].begin(), s[i].end());
		cout << s[i].size() << ' ';
		for(auto j : s[i]){
			cout << j << ' ';
		}
		cout << endl;
	}
	return 0;
}
例3

求细胞数量

https://www.luogu.com.cn/problem/P1451

解3

本质就是求连通块数。要注意边界 invalid 函数用于判断当前点是否合法（在图的范围里）且该被访问（先前未被访问且是细胞的部分）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
#define N 107
using namespace std;

int n, m, vis[N][N], a[N][N];

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

inline bool invalid(int x, int y){
	return x <= 0 || x > n || y <= 0 || y > m || a[x][y] == 0 || vis[x][y];
}

inline int dfs(int x, int y){
	vis[x][y] = 1;
	for(int i = 0; i < 4; ++i){
		 int tx = x + dx[i];
		 int ty = y + dy[i];
		 if(!invalid(tx, ty)) {dfs(tx, ty);}
	}
}


inline int rd(){
	char c = getchar();
	while(!isdigit(c)) c = getchar();
	return c - '0';
}

int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j) a[i][j] = rd();

	int cnt = 0;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j)
			if(!invalid(i, j)) {dfs(i, j); ++cnt;}
	}
	
	cout << cnt << endl;
	return 0;
}
BFS

广度优先搜索 —— ”谁离我近（最短的距离）谁先出“

例1

求细胞数量

https://www.luogu.com.cn/problem/P1451

解1

本质就是求连通块数。要注意边界 invalid 函数用于判断当前点是否合法（在图的范围里）且该被访问（先前未被访问且是细胞的部分）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define N 107
using namespace std;

queue<pair<int, int> > s;

int n, m, vis[N][N], a[N][N];

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

inline bool invalid(int x, int y){
	return x <= 0 || x > n || y <= 0 || y > m || a[x][y] == 0 || vis[x][y];
}

inline void bfs(int x, int y){
	vis[x][y] = 1;
	s.push(make_pair(x, y));
	while(!s.empty()){
		pair<int, int> t = s.front();
		s.pop();
		for(int i = 0; i < 4; ++i){
			int tx = dx[i] + t.first;
			int ty = dy[i] + t.second;
			if(!invalid(tx, ty)) {vis[tx][ty] = 1; s.push(make_pair(tx, ty));}
		}
	}
}

inline int rd(){
	char c = getchar();
	while(!isdigit(c)) c = getchar();
	return c - '0';
}

int main(){
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j) a[i][j] = rd();

	int cnt = 0;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j)
			if(!invalid(i, j)) {++cnt; bfs(i, j);}
	}
	
	printf("%d", cnt);
	return 0;
}
例2

Eva.oj 0004

给一个 个点的无向图，输出连通块数，接下来 行，输出各个连通块所含点的数量，且按从小到大的顺序输出该连通块中点的编号。

Input Format

第一行两个整数 。代表这个图有 个点， 条边。接下来 行，每行两个整数 代表有一条边连接 和 。

Output Format

第一行输出连通块数。接下来 行，每行若干个数字。第一个数字，代表连通块所含点的数量，后面按从小到的顺序，输出该连通块中点的编号。

解2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define N 100007
using namespace std;

int vis[N];

queue<int> q; 

vector<int> a[N], s[N];

inline void bfs(int x, int num){
	vis[x] = num;
	s[num].push_back(x);
	q.push(x);
	while(!q.empty()){
		int t = q.front();
		q.pop();
		for(auto i : a[t]){
			if(!vis[i]) {vis[i] = num; q.push(i); s[num].push_back(i);}
		} 
	}
}

int main(){
	int m, n;
	cin >> n >> m;
	for(int i = 1; i <= m; ++i){
		int u, v;
		cin >> u >> v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	
	int cnt = 0;
	for(int i = 1; i <= n; ++i){
		if(!vis[i]) {bfs(i, ++cnt);}
	}
	cout << cnt << endl;
	
	for(int i = 1; i <= cnt; ++i){
		sort(s[i].begin(), s[i].end());
		cout << s[i].size() << ' ';
		for(auto j : s[i]){
			cout << j << ' ';
		}
		cout << endl;
	}
	return 0;
}
练练练
例1

海战

https://www.luogu.com.cn/problem/P1331

解1（bfs）

保证连通块都是方形的。

我的思路：判断存不存在不合法的点。即那种类似于三角直尺的点。

Co老师的思路：记一下该连通块，上下左右四个边界，看连通块的大小是否等于边界围成的面积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
#define N 1007
using namespace std;

queue<pair<int, int> > s;

int n, m, vis[N][N], a[N][N];

const int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1};
const int dy[8] = {0, 0, -1, 1, 1, -1, 1, -1};

inline bool invalid(int x, int y){
	return x <= 0 || x > n || y <= 0 || y > m || a[x][y] == 0 || vis[x][y];
}

inline bool valid(int x, int y){
	for(int i = 4; i < 8; ++i){
		int tx = x + dx[i];
		int ty = y + dy[i];
		if(tx <= 0 || tx > n || ty <= 0 || ty > m || vis[tx][ty] == 1) continue;
		if(i == 4 && vis[x - 1][y] == 1 && vis[x][y + 1] == 1) return 0;
		else if(i == 5 && vis[x - 1][y] == 1 && vis[x][y - 1] == 1) return 0;
		else if(i == 6 && vis[x + 1][y] == 1 && vis[x][y + 1] == 1) return 0;
		else if(i == 7 && vis[x + 1][y] == 1 && vis[x][y - 1] == 1) return 0;
	}
	return 1;
}

inline void bfs(int x, int y){
	vis[x][y] = 1;
	s.push(make_pair(x, y));
	while(!s.empty()){
		pair<int, int> t = s.front();
		s.pop();
		for(int i = 0; i < 4; ++i){
			int tx = dx[i] + t.first;
			int ty = dy[i] + t.second;
			if(!invalid(tx, ty)) {vis[tx][ty] = 1; s.push(make_pair(tx, ty));}
		}
	}
}

inline int rd(){
	char c = getchar();
	while(c != '.' && c != '#') c = getchar();
	if(c == '.') return 0;
	else if(c == '#') return 1;
}

int main(){
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j) a[i][j] = rd();

	int cnt = 0;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j)
			if(!invalid(i, j)) {++cnt; bfs(i, j);}
	}
	
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			if(vis[i][j] == 1 && !valid(i, j)){
				printf("Bad placement.");
				return 0;
			}
		}
	}
	
	printf("There are %d ships.", cnt);
	return 0;
}
解2（dfs）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#define N 1007
using namespace std;

int n, m, vis[N][N], a[N][N];

const int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1};
const int dy[8] = {0, 0, -1, 1, 1, -1, 1, -1};

inline bool invalid(int x, int y){
	return x <= 0 || x > n || y <= 0 || y > m || a[x][y] == 0 || vis[x][y];
}

inline bool valid(int x, int y){
	for(int i = 4; i < 8; ++i){
		int tx = x + dx[i];
		int ty = y + dy[i];
		if(tx <= 0 || tx > n || ty <= 0 || ty > m || vis[tx][ty] == 1) continue;
		if(i == 4 && vis[x - 1][y] == 1 && vis[x][y + 1] == 1) return 0;
		else if(i == 5 && vis[x - 1][y] == 1 && vis[x][y - 1] == 1) return 0;
		else if(i == 6 && vis[x + 1][y] == 1 && vis[x][y + 1] == 1) return 0;
		else if(i == 7 && vis[x + 1][y] == 1 && vis[x][y - 1] == 1) return 0;
	}
	return 1;
}

inline void dfs(int x, int y){
	vis[x][y] = 1;
	for(int i = 0; i < 4; ++i){
		int tx = x + dx[i];
		int ty = y + dy[i];
		if(!invalid(tx, ty)) dfs(tx, ty);
	}
}

inline int rd(){
	char c = getchar();
	while(c != '.' && c != '#') c = getchar();
	if(c == '.') return 0;
	else if(c == '#') return 1;
}

int main(){
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j) a[i][j] = rd();

	int cnt = 0;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j)
			if(!invalid(i, j)) {++cnt; dfs(i, j);}
	}
	
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			if(vis[i][j] == 1 && !valid(i, j)){
				printf("Bad placement.");
				return 0;
			}
		}
	}
	
	printf("There are %d ships.", cnt);
	return 0;
}
例2

填涂颜色

https://www.luogu.com.cn/problem/P1162

解2（dfs）

题意：被 包围的 输出用 ，其余 还是输出 。保证该图中只有一个由 围成的圈。

思路：从边界的 开始搜索，凡是搜到的点一定不在圈里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
#define N 1007
using namespace std;

int n, vis[N][N], a[N][N];

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

inline bool invalid(int x, int y){
	return x <= 0 || x > n || y <= 0 || y > n || a[x][y] == 1 || vis[x][y];
}

inline void dfs(int x, int y){
	vis[x][y] = 1;
	for(int i = 0; i < 4; ++i){
		int tx = x + dx[i];
		int ty = y + dy[i];
		if(!invalid(tx, ty)) dfs(tx, ty);
	}
}

inline int rd(){
	char c = getchar();
	while(!isdigit(c)) c = getchar();
	return c - '0';
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j) a[i][j] = rd();
	
	for(int i = 1; i <= n; ++i){
		if(a[i][1] == 0 && vis[i][1] == 0) dfs(i, 1);
		if(a[i][n] == 0 && vis[i][n] == 0) dfs(i, n);
		if(a[1][i] == 0 && vis[1][i] == 0) dfs(1, i);
		if(a[n][i] == 0 && vis[n][i] == 0) dfs(n, i);
	}
	
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= n; ++j){
			if(j == 1){
				if(a[i][j] == 1) printf("1");
				else if(a[i][j] == 0 && vis[i][j] == 1) printf("0");
				else printf("2");
			}else{
				if(a[i][j] == 1) printf(" 1");
				else if(a[i][j] == 0 && vis[i][j] == 1) printf(" 0");
				else printf(" 2");
			}
		}
		printf("\n");
	}
	
	return 0;
}
解2（bfs）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
#define N 1007
using namespace std;

queue<pair<int, int> > q;

int n, vis[N][N], a[N][N];

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

inline bool invalid(int x, int y){
	return x <= 0 || x > n || y <= 0 || y > n || a[x][y] == 1 || vis[x][y];
}

inline void bfs(int x, int y){
	vis[x][y] = 1;
	q.push(make_pair(x, y));
	while(!q.empty()){
		pair<int, int> t = q.front();
		q.pop();
		for(int i = 0; i < 4; ++i){
			int tx = t.first + dx[i];
			int ty = t.second + dy[i];
			if(!invalid(tx, ty)){
				vis[tx][ty] = 1;
				q.push(make_pair(tx, ty));	
			}
		}
	}
}

inline int rd(){
	char c = getchar();
	while(!isdigit(c)) c = getchar();
	return c - '0';
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j) a[i][j] = rd();
	
	for(int i = 1; i <= n; ++i){
		if(a[i][1] == 0 && vis[i][1] == 0) bfs(i, 1);
		if(a[i][n] == 0 && vis[i][n] == 0) bfs(i, n);
		if(a[1][i] == 0 && vis[1][i] == 0) bfs(1, i);
		if(a[n][i] == 0 && vis[n][i] == 0) bfs(n, i);
	}
	
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= n; ++j){
			if(j == 1){
				if(a[i][j] == 1) printf("1");
				else if(a[i][j] == 0 && vis[i][j] == 1) printf("0");
				else printf("2");
			}else{
				if(a[i][j] == 1) printf(" 1");
				else if(a[i][j] == 0 && vis[i][j] == 1) printf(" 0");
				else printf(" 2");
			}
		}
		printf("\n");
	}
	
	return 0;
}
例3

我觉得，是个求最短路

https://codeforces.com/problemset/problem/689/B

解3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
#define N 200007
using namespace std;

queue<int> q; 

vector<int> a[N];

int n, vis[N];

inline void bfs(int x){
    vis[x] = 0;
	q.push(x);
	while(!q.empty()){
		int t = q.front();
		q.pop();
		for(auto i : a[t]){
			if(vis[i] == -1) {vis[i] = vis[t] + 1; q.push(i);}
		} 
	}
}

int main(){
	scanf("%d, %d", &n);
	for(int i = 1; i <= n; ++i){
		vis[i] = -1;
		int u;
		cin >> u;
		if(u != i) a[i].push_back(u);
		if(i == 1) a[i].push_back(i + 1);
		else if(i == n) a[i].push_back(i - 1);
		else{
			a[i].push_back(i + 1);
			a[i].push_back(i - 1);
		}
	}
	bfs(1);
	for(int i = 1; i <= n; ++i){
		printf("%d ", vis[i]);
	}
	return 0;
}


做题有点上瘾……

  • Post title：图论
  • Post author：Eva.Q
  • Create time：2021-08-24 09:55:46
  • Post link：https://qyy/2021/08/24/Algorithm/ColinClass5/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.