文章
20
粉丝
412
获赞
12
访问
163.2k
#include <iostream>
using namespace std;
const int MAXN = 1005;
int fa[MAXN]; //存储每个元素的父节点
int rk[MAXN]; //记录每个根节点对应的树的深度
void init(int n) { //初始化
for(int i = 1;i <= n;i++) {
fa[i] = i;
rk[i] = 1;
}
}
int Find(int x) { //查找(路径压缩)
if(fa[x] == x)
return x;
else {
fa[x] = Find(fa[x]); //将x的父节点设置成根节点
return fa[x];
}
}
int Merge(int i, int j) { //合并(按秩合并)
int x = Find(i);
int y = Find(j);
if(rk[x] <= rk[y])
fa[x] = y;
else fa[y] = x;
if(rk[x] == rk[y] && x != y)
rk[y]++; //如果深度相同且根节点不同,则新的根节点的深度+1
}
int main() {
int n, m, x, y, root;
while(cin >> n >> m) {
init(n);
for(int i = 0;i < m;i++) {
cin >> x >> y;
Merge(x, y);
}
root = 0;
for(int i = 1;i <= n;i++)
if(fa[i] == i) root++;
if(root == 1) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
登录后发布评论
暂无评论,来抢沙发