文章

20

粉丝

412

获赞

12

访问

163.2k

头像
并查集优化(路径压缩+按秩合并)
推荐阅读
P1367 吉林大学机试题
发布于2021年4月25日 16:37
阅读数 6.8k

#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;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发