union.cpp

一些重要的数据结构

int		set[maxn],rank[maxn];
void	newset(int n){ for(i=0; i<n; i++) set[i]=i; }
int		find(int i){
		int j, k, t;
		for (k=i; set[k]!=k; k=set[k]);
		for (j=i; j!=k; j=t){ t = set[j]; set[j] = k; }
		return k;
}
void	join(int i, int j){
		i = find(i); j = find(j);
		if (i==j) return;		
		if (rank[i]<=rank[j]){
			set[i] = j;
			if (rank[i]==rank[j]) rank[j]++;
		} else set[j] = i;
}