解题思路:
判断连通图,构建并查集即可
注意事项:
参考代码:
#include <iostream> #include <cstring> using namespace std; int arr[1050]; bool vis[1050]; int root(int x) { int r = x; while (arr[r] != r) { //寻找祖先 r = arr[r]; } int i = x, j; while (i != r) { //路径压缩 j = arr[i]; arr[i] = r; i = j; } return r; } int main() { int n, m; while (cin >> n >> m && n && m) { for (int i = 1; i <= 1050; i++) //初始化 arr[i] = i; memset(vis, 0, sizeof(vis)); for (int i = 1; i <= m; i++) { int a, b; cin >> a >> b; int fx = root(a); int fy = root(b); arr[fx] = fy; } for (int i = 1; i <= n; i++) {//标记祖先 vis[root(i)] = 1; } int ans = 0; for (int i = 1; i <= n; i++) { // 查找有多少个祖先,则连通图则有几个 if (vis[i]) { ans++; } } if (ans == 1) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }
0.0分
3 人评分
C语言训练-谁家孩子跑最慢* (C语言代码)浏览:1508 |
校门外的树 (C语言代码)浏览:1119 |
C语言考试练习题_排列 (C语言代码)浏览:1317 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:599 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:1000 |
printf基础练习2 (C语言代码)浏览:644 |
【绝对值排序】 (C语言代码)浏览:820 |
1642题解浏览:714 |
printf基础练习2 (C语言代码)浏览:503 |
A+B for Input-Output Practice (I) (C语言代码)浏览:429 |