1050朋友圈和1051虚拟朋友这两题是并查集的题，不过课上没有讲这个知识点，作业也没有布置，所以先跳过，放在下一篇和最小生成树一起

1052-1054是dfs和bfs的题，其实和树没啥区别，不过图的题很多都是无向图，但是要标记点是否已访问（一般是一个visited数组），防止死循环

1052. 哥尼斯堡的七桥问题

判断有没有欧拉回路，或者说判断图是不是欧拉图（整张图可以从一个点一笔画走完并回到起点）需要干两件事情：

1. 判断图的连通性
2. 数每个点的度数，需要满足每个点的度数都是偶数（存每条边的时候给两个端点的度数都加一即可）

判断图的连通性可以用dfs或者并查集

dfs做法：

#include <bits/stdc++.h>
using namespace std;

vector<int> G[1003];
bool visited[1003];
int cnt[1003] = {0};

void dfs(int u) {
	visited[u] = 1;
	for (int v:G[u]) {
		if (!visited[v]) {
			dfs(v);
		}
	}
}

int main() {
	int n,m,u,v;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
		cnt[u]++;
		cnt[v]++;
	}
	
	for (int i = 1; i <= n; i++)
		if (cnt[i] % 2) {
			cout << 0 << endl;
			return 0;
		} 
	
	dfs(1); //从点1出发跑一次dfs，如果能访问所有点，那么visited数组应该都是1，否则说明有的点到不了，也就是图不连通

	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			cout << 0 << endl;
			return 0;
		}
	}
	
	cout << 1 << endl;
	return 0;
}

并查集做法：

#include <bits/stdc++.h>
using namespace std;

int cnt[1005] = {0};
int root[1005] = {0};

int Findroot(int x) {
    if (x != root[x]) {
        root[x] = Findroot(root[x]); 
    }
    return root[x];
}

void Merge(int x,int y) {
	int rootx = Findroot(x);
	int rooty = Findroot(y);
	root[rootx] = rooty;
}

int main() {
	int n,m;
	cin >> n >> m;
	for (int i = 1;i <= n;i++) {
		root[i] = i;
	}
	
	while (m--) {
		int u,v;
		cin >> u >> v;
		cnt[u]++;
		cnt[v]++;
		Merge(u,v); 
	}
	
	int c = 0;
	for (int i = 1;i <= n;i++) {
		if (Findroot(i) == i) {
			c++;
		}
	}
	
	if (c > 1) {
		cout << 0;
		return 0;
	}
	
	for (int i = 1; i <= n;i++) {
		if (cnt[i] % 2) {
			cout << 0;
			return 0;
		}
	}
	cout << 1;
	return 0;
}

1053. 地下迷宫探索

比较绕的一道dfs题，需要注意两个要点：

1. 以节点小编号优先的次序访问（点灯），邻接表存图后可以把每个结点的邻接数组先排个序，这样dfs遍历的时候就有序了
2. “去程”和“返程”都要输出一遍灯的编号，代码实现的时候可以在dfs遍历邻居的前后都输出一遍结点编号

#include <bits/stdc++.h>
using namespace std;

bool visited[1003] = {false};
int ans[1003] = {0};

int pnt = 0;

void dfs(int u, vector<vector<int>>& g) {
	visited[u] = true;
	cout << u << " ";
	
	for (auto& node : g[u]) {
		if (!visited[node]) {
			dfs(node,g);
			cout << u << " ";
		}
	}
} 

int main() {
	int n,m,s;
	cin >> n >> m >> s;
	vector<vector<int>> g(n+1, vector<int>(0));
	
	for(int i = 0;i < m;i++) {
		int u,v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	
	for (int i = 1;i <= n;i++){
		sort(g[i].begin(),g[i].end());
	}	
	dfs(s,g);
	
	for (int i = 1; i <= n;i++){
		if (!visited[i]) {
			cout << 0 << endl;
			break;
		}
	}
	
	return 0;
}

1054. 六度空间

bfs的题，假设起点为node，先设一个dis数组，dis[i]表示从node出发到点i的距离，一开始全都初始化为-1表示不可达，dis[node]设为0

然后跑bfs，每次取出队首，把队首的相邻点加入队列（只要到六层，也就是dis<=6就可以了）

#include <bits/stdc++.h>
using namespace std;

int n,m;

int BFS(int node,vector<vector<int>>&G) {
	vector<int> dis(n+1,-1);
	dis[node] = 0;
	int cnt = 1;
	queue<int> q;
	q.push(node);
	
	while (!q.empty()) {
		int curr = q.front();
		q.pop();
		for (auto p:G[curr]) {
			if (dis[p] == -1) {
				dis[p] = dis[curr] + 1;
				if (dis[p] <= 6) {
					cnt++;
					q.push(p);
				} 
			}
		}
	}
	return cnt;
}

int main() {
	cin >> n >> m;
	vector<vector<int>> G(n+1);
	int a,b;
	for (int i = 0;i < m;i++) {
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	
	for (int i = 1;i <= n;i++) {
		int cnt = BFS(i,G);
		double per = (double(cnt)/n) * 100;
		printf("%d: %.2f%%\n",i,per);
    }
    
	return 0;
}