AcWing 3587：连通图 ← 吉林大学考研机试题 + DFS

​【题目来源】
https://www.acwing.com/problem/content/3590/

【题目描述】
给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。

【输入格式】
输入包含若干组数据。
每组数据第一行包含两个整数 n 和 m，表示无向图的点和边数。
接下来 m 行，每行包含两个整数 x，y，表示点 x 和点 y 相连。
点的编号从 1 到 n。
图中可能存在重边和自环。

【输出格式】
每组数据输出一行，一个结果，如果所有顶点都是连通的，输出 YES，否则输出 NO。

【输入样例】
4 3
1 2
2 3
3 2
3 2
1 2
2 3

【输出样例】
NO
YES

【数据范围】
输入最多包含 10 组数据。
1≤n≤1000，
1≤m≤5000，
1≤x，y≤n

【算法分析】
本题的“并查集”实现，详见：https://blog.csdn.net/hnjzsyjyj/article/details/126455868

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int N=1e3+5;
vector<int> g[N];
bool st[N];void dfs(int u) {st[u]=true;for(int j:g[u]) {if(!st[j]) dfs(j);}
}int main() {int n,m;while(cin>>n>>m) {memset(st,false,sizeof st);for(int i=1; i<=n; i++) {g[i].clear();}while(m--) {int x,y;cin>>x>>y;g[x].push_back(y);g[y].push_back(x);}dfs(1);bool flag=true;for(int i=1; i<=n; i++) {if(!st[i]) {flag=false;break;}}cout<<(flag?"YES":"NO")<<endl;}return 0;
}/*
in:
4 3
1 2
2 3
3 2
3 2
1 2
2 3out:
NO
YES
*/

 

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/126455868

 

 

 

​