连通图（暑假每日一题 21）

连通图（暑假每日一题 21）

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

输入格式 输入包含若干组数据。

图中可能存在重边和自环。

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

输入样例：

4 31 22 33 23 21 22 3

输出样例：

NOYES

#include#includeusing namespace std;const int N = 1010;int n, m;bool g[N][N], st[N];void dfs(int u){ st[u] = true; for(int i = 1; i <= n; i++) if(!st[i] && g[u][i]) dfs(i);}int main(){ while (cin >> n >> m){ memset(g, 0, sizeof g); memset(st, 0, sizeof st); int a, b; for(int i = 0; i < m; i++) cin >> a >> b, g[a][b] = g[b][a] = true; int cnt = 0; for(int i = 1; i <= n; i++){ if(!st[i]) { cnt++; if(cnt > 1) break; dfs(i); } } if(cnt > 1) puts("NO"); else puts("YES"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。