Blog

并查集

union-find sets

Posted by BY on September 29, 2018

前言

并查集并不算难的问题，是个很常见很基础的问题，一直都没有好好思考这个问题。

正文

问题来源

在看友人博客的时候看到这么一个问题，杭电OJ 1856题。后来思考到原先的分组项目中也适合这个场景，所以要好好学习学习。

问题简要描述

朋友在一个集合，朋友的朋友也是朋友，求元素最多的集合的元素个数。

分析与代码

并查集 英文：Disjoint Set，即“不相交集合”
将编号分别为1…N的N个对象划分为不相交集合，
在每个集合中，选择其中某个元素代表所在集合。

常见两种操作：
合并两个集合
查找某元素属于哪个集合

并查集实现的程序代码:

int set[MAXN],rank[MAXN]; //set[i]=k表示i的父节点是k，rank[]存储树的深度。
int FindSet(int x)
{
    if(set[x]!=x)
        set[x]=FindSet(set[x]);
    return set[x];
}//寻找x的根节点

void MakeSet(int x)
{
    set[x]=x;
    rank[x]=1;
}//初始化，各节点都是孤立的

void Link(int a,int b)
{  //合并时判段rank[a],rank[b]的大小，以减小树的高度
    if(rank[a]>rank[b])  
        set[b]=a;
    else if(rank[a]<rank[b])
        set[a]=b;
    else
    {
        set[a]=b;
        rank[b]++;
    }
}

void Union(int a,int b)
{
    Link(FindSet(a),FindSet(b));
}

Find的时间复杂度取决于树的高度.在实际中,由于多次Union操作,容易导致树的高度越来越大,
从而降低Find的执行效率. 实际上在并查集中,树的具体结构并不重要,只要维持树所包含的结点不变即可

#include<stdio.h>
int rank[10000000];
int set[10000000];
int max;
int find(int x) {
	if (x != set[x]) {
		set[x] = find(set[x]);
	}
	return set[x];
}
void merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return;
	if (rank[x]>rank[y]) {
		set[y] = x;
		rank[x] += rank[y];
		if (max < rank[x]) {
			max = rank[x];
		}
	}
	else {
		set[x] = y;
		rank[y] += rank[x];
		if (max < rank[y]) {
			max = rank[y];
		}
	}
} 
int main() {
	int n;
	int i;
	int a[100000];
	int b[100000];
	while(scanf("%d",&n)!=EOF) {
		if(n==0) {//不要忘了这个判断
			printf("1\n");
			continue;
		}
		max = 0;
		for (i=0;i<n;i++) {
			scanf("%d %d",&a[i],&b[i]);
			rank[a[i]] = rank[b[i]] = 1;
			set[a[i]] = a[i];
			set[b[i]] = b[i];
		}
		for (i=0;i<n;i++) {
			merge(a[i],b[i]);
		}
		printf("%d\n",max);
	}
}

总结

写并查集时涉及到的路径压缩，最好用递归，一方面代码的可读性非常好，另一方面，可以更直观的理解路径压缩时在回溯时完成的巧妙。

结语

查漏补缺。

CATALOG
    FEATURED TAGS
    Blog