【题目来源】
https://www.acwing.com/problem/content/3590/
【题目描述】
给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。
【输入格式】
输入包含若干组数据。
每组数据第一行包含两个整数 n 和 m，表示无向图的点和边数。
接下来 m 行，每行包含两个整数 x,y，表示点 x 和点 y 相连。
点的编号从 1 到 n。
图中可能存在重边和自环。
【输出格式】
每组数据输出一行，一个结果，如果所有顶点都是连通的，输出 YES，否则输出 NO。
【数据范围】
输入最多包含 10 组数据。
1≤n≤1000,
1≤m≤5000,
1≤x,y≤n
【输入样例】
4 3
1 2
2 3
3 2
3 2
1 2
2 3
【输出样例】
NO
YES
【算法分析】
● 本题的“并查集”代码实现详见：https://blog.csdn.net/hnjzsyjyj/article/details/126455868
● 本题利用 dfs 判断连通图的原理在于“dfs必然能够遍历到连通图的所有点”。如果有点没有被遍历到，说明不连通。
【算法代码：dfs+链式前向星】
● dfs算法模板：https://blog.csdn.net/hnjzsyjyj/article/details/118736059
● 链式前向星详见：https://blog.csdn.net/hnjzsyjyj/article/details/139369904
#include <bits/stdc++.h>
using namespace std;const int N=1e3+5;
const int M=5e3+5;
int e[M<<1],ne[M<<1],h[N],idx;
bool st[N];
int n,m;void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}void dfs(int u) {st[u]=1;for(int i=h[u]; i!=-1; i=ne[i]) {int j=e[i];if(!st[j]) dfs(j);}
}int main() {while(cin>>n>>m) {memset(st,false,sizeof st);memset(h,-1,sizeof h);idx=0;while(m--) {int a,b;cin>>a>>b;add(a,b),add(b,a);}dfs(1);bool flag=true;for(int i=1; i<=n; i++)if(!st[i]) {flag=false;break;}if(flag) cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
}/*
in:
4 3
1 2
2 3
3 2
3 2
1 2
2 3out:
NO
YES
*/【算法代码：dfs+邻接矩阵】
● dfs算法模板：https://blog.csdn.net/hnjzsyjyj/article/details/118736059
● 无向无权图的邻接矩阵实现：https://blog.csdn.net/hnjzsyjyj/article/details/116245897
#include <bits/stdc++.h>
using namespace std;const int N=1010;
int g[N][N];
bool st[N];
int n,m;void dfs(int u) {st[u]=true;for(int i=1; i<=n; i++)if(!st[i] && g[u][i]!=0) dfs(i);
}int main() {while(cin>>n>>m) {memset(g,0,sizeof g);memset(st,false,sizeof st);int x,y;while(m--) {cin>>x>>y;g[x][y]=g[y][x]=1;}dfs(1);int i;for(i=1; i<=n; i++) {if(!st[i]) break;}if(i<=n) cout<<"NO"<<endl;else cout<<"YES"<<endl;}return 0;
}/*
in:
4 3
1 2
2 3
3 2
3 2
1 2
2 3out:
NO
YES
*/
【参考文献】
https://www.acwing.com/solution/content/124095/
https://blog.csdn.net/hnjzsyjyj/article/details/118736059
https://blog.csdn.net/hnjzsyjyj/article/details/139369904
