64 lines
1.6 KiB
C++
64 lines
1.6 KiB
C++
|
#include <bits/stdc++.h>
|
|||
|
|
|
|||
|
|
using namespace std;
|
|||
|
|
|
|||
|
|
const int N = 1010; // 图的最大点数量
|
|||
|
|
/**
|
|||
|
|
共提供两组数据，样例1为不连通用例，样例2为连通用例
|
|||
|
|
|
|||
|
|
样例1：不连通，5号结点为独立的
|
|||
|
|
5 4
|
|||
|
|
1 2
|
|||
|
|
2 3
|
|||
|
|
3 4
|
|||
|
|
1 4
|
|||
|
|
|
|||
|
|
样例2：连通，不存在独立结点
|
|||
|
|
5 4
|
|||
|
|
1 2
|
|||
|
|
2 3
|
|||
|
|
3 4
|
|||
|
|
1 5
|
|||
|
|
|
|||
|
|
检测各种算法是否能准确获取结果
|
|||
|
|
*/
|
|||
|
|
int n; // n个人
|
|||
|
|
int m; // m个亲戚
|
|||
|
|
int x, y; // 输入两个人之间的关系
|
|||
|
|
int p[N]; // 并查集数组
|
|||
|
|
// 要深入理解这个递归并压缩的过程
|
|||
|
|
int find(int x) {
|
|||
|
|
if (p[x] != x) // 如果x不是族长,递归找父亲,副产品就是找回的结果更新掉自己的家族信息。
|
|||
|
|
p[x] = find(p[x]); // 非常经典的更新,路径压缩大法！
|
|||
|
|
// 返回族长是谁
|
|||
|
|
return p[x];
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
int cnt;
|
|||
|
|
|
|||
|
|
int main() {
|
|||
|
|
#ifndef ONLINE_JUDGE
|
|||
|
|
// freopen("in1.in", "r", stdin);
|
|||
|
|
freopen("in2.in", "r", stdin);
|
|||
|
|
#endif
|
|||
|
|
// n个人员，m个关系
|
|||
|
|
cin >> n >> m;
|
|||
|
|
// 并查集初始化
|
|||
|
|
for (int i = 1; i <= n; i++) p[i] = i; // 自己是自己的老大
|
|||
|
|
// 录入m种关系,使用并查集来判断图的连通性
|
|||
|
|
for (int i = 1; i <= m; i++) {
|
|||
|
|
cin >> x >> y;
|
|||
|
|
// 加入并查集
|
|||
|
|
int px = find(x), py = find(y);
|
|||
|
|
if (px != py) p[px] = py;
|
|||
|
|
}
|
|||
|
|
// 图已经搭好了，接下来看它们根节点是否相同，如只有一个相同的根节点，则说明是一个连通图
|
|||
|
|
for (int i = 1; i <= n; i++)
|
|||
|
|
if (p[i] == i) cnt++;
|
|||
|
|
|
|||
|
|
if (cnt == 1)
|
|||
|
|
printf("图是连通的\n");
|
|||
|
|
else
|
|||
|
|
printf("图不是连通的\n");
|
|||
|
|
return 0;
|
|||
|
|
}
|