ʕ·͡ˑ·ཻ ʕ•̫͡• ʔ•̫͡•ཻʕ•̫͡•ʔ•͓͡•ʔ

算法理解

​ 并查集是一种树型的数据结构，用于处理一些不交集的合并和查询问题。联合-查找算法(union-find algorithm)定义了两个用于此数据结构的操作。

  • Union: 将两个子集合并成同一个集合，根据父节点的引用像根行进直到树根。
  • Find: 确定元素属于哪一个集合，方法就是不断的向上查找找到它的根节点，确定两个元素是否在同一个子集，将两棵树合并到一起，这通过将一颗树的根连接到另一棵树的根。

​ 在并查集树中，每个集合的代表即是集合的根节点。

初始化

1
2
for(int i=1;i<=n;i++)
    pre[i]=i;//使每一个点的父结点都指向自己

查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//递归
int find(int x)
{
    if(pre[x]==x) return x;
    return find(find(x));
}

//非递归
int find(int x)
{
    int r=x;//将当前位置记录
    while(pre(r)!=r) //如果不是根节点
    r=pre(r);//继续向上查找，r的值更新为其父结点
    return r;
}

但是这样写数据量大的时候会爆，下面来看路径压缩优化：

路径压缩优化

将某个根结点下的所有子结点都指向该根结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int find(int x)
{
    int r=x;
    while(pre[r]!=r)
    {
        r=pre[r];
    }
    int i=x;//记录当前点
    int j;//记录i的上家
    while(i!=r)//若当前点不是根结点
    {
        j=pre[i];//记录上家
        pre[i]=r;//使当前点直接指向根节点
        i=j;//当前点移动到上家
    }
    return r;
}

合并

1
2
3
4
5
6
void merge(int x,int y)    //合并集合 
{
    int t1=find(x);    //找到x和y的根结点 
    int t2=find(y);
    if(t1!=t2)    pre[t1]=t2; //所在集合不同，将其中一个作为另一个集合的子集(根结点一样)
}

例题：

A - How Many Tables

Today is Ignatius’ birthday. He invites a lot of friends. Now it’s dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers.

One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table.

For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.

Input

The input starts with an integer T(1<=T<=25) which indicate the number of test cases. Then T test cases follow. Each test case starts with two integers N and M(1<=N,M<=1000). N indicates the number of friends, the friends are marked from 1 to N. Then M lines follow. Each line consists of two integers A and B(A!=B), that means friend A and friend B know each other. There will be a blank line between two cases.

Output

For each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks.

Sample Input

1
2
3
4
5
6
7
8
2
5 3
1 2
2 3
4 5

5 1
2 5

Sample Output

1
2
2
4

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
using namespace std;
const int maxn = 1050;
int s[maxn];
void init_set(){
	for(int i=1;i<maxn;i++)
	    s[i]=i;
}
int find_set(int x){
	return x==s[x]?x:find_set(s[x]);
}
void union_set(int x,int y){
	x=find_set(x);
	y=find_set(y);
	if(x!=y) s[x]=s[y];
}
int main(){
	int t,m,n,x,y;
	cin>>t;
	while(t--){
		cin>>n>>m;
		init_set();
		for(int i=1;i<=m;i++){
			cin>>x>>y;
			union_set(x,y);
		}
		int ans=0;
		for(int i=1;i<=n;i++){
			if(s[i]==i) ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
}

B - Ubiquitous Religions

There are so many different religions in the world today that it is difficult to keep track of them all. You are interested in finding out how many different religions students in your university believe in.

You know that there are n students in your university (0 < n <= 50000). It is infeasible for you to ask every student their religious beliefs. Furthermore, many students are not comfortable expressing their beliefs. One way to avoid these problems is to ask m (0 <= m <= n(n-1)/2) pairs of students and ask them whether they believe in the same religion (e.g. they may know if they both attend the same church). From this data, you may not know what each person believes in, but you can get an idea of the upper bound of how many different religions can be possibly represented on campus. You may assume that each student subscribes to at most one religion.

Input

The input consists of a number of cases. Each case starts with a line specifying the integers n and m. The next m lines each consists of two integers i and j, specifying that students i and j believe in the same religion. The students are numbered 1 to n. The end of input is specified by a line in which n = m = 0.

Output

For each test case, print on a single line the case number (starting with 1) followed by the maximum number of different religions that the students in the university believe in.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
10 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
10 4
2 3
4 5
4 8
5 8
0 0

Sample Output

1
2
Case 1: 1
Case 2: 7

Hint

Huge input, scanf is recommended.

题目大意:

有 n 个学生，编号 1\sim n，每个学生最多有 1 个宗教信仰，输入 m 组数据，每组数据包含 a,b，表示同学 a 和同学 b 有相同的信仰，求在 n 名学生中最多存在多少种不同的宗教信仰。

思路：

与A题一样。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
using namespace std;
const int maxn = 50000+5;
int s[maxn];
int height[maxn];
void init_set(){
	for(int i = 1;i<=maxn;i++){
		s[i]=i;
		height[i]=0;
	}
}
int find_set(int x){		
	return x == s[x] ? x:find_set(s[x]);
}
void union_set(int x,int y){
	x = find_set(x);
	y = find_set(y);
	if(height[x] == height[y]){
		height[x] = height[x] + 1;
		s[y] = x;
	}else{
		if(height[x] < height [y]) s[x] = y;
		else s[y] = x;
	}
}
 
int main(){
	int t,n,m,x,y;
	int k=1;
	while(cin >> n >>m &&m&&n){
		init_set();
		for(int i = 1;i<=m;i++){
			cin >>x>>y;
			union_set(x,y);
		}
		int ans = 0;
		for(int i=1;i<=n;i++){	
			if(s[i] == i)
				ans++;
		}
		cout<<"Case "<<k++<<": "<<ans<<endl;
	}
	return 0;
}

 Previous

带权并查集