The Suspects POJ - 1611(并查集模板题)

116 阅读 0 评论 77 点赞

我是靠谱客的博主从容电灯胆，这篇文章主要介绍The Suspects POJ - 1611(并查集模板题)，现在分享给大家，希望可以做个参考。

The Suspects

思路：

这是一道典型的并查集问题，在我看来并查集问题，像是一群儿子和一个爸爸的问题，不扯了，这道题的主要思路为，将所有的点连成父子关系，看一看0的爸爸是谁，然后判断一下都谁和0的爸爸是一个，那么就会患病，0的爸爸也会患病，因此别忘了。

代码：

繁琐版：

复制代码

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>
#include<cstdio>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<queue>
#include<vector>
#define ll long long
#define mes(x,y) memset(x,y,sizeof(x))
using namespace std;
ll fish[1000040],lv[40000];
int head(int p){
	if(fish[p]!=p)fish[p]=head(fish[p]);
	return fish[p];
}//搜索爸爸是哪个
void cmb(int a,int b){
	int la=head(a),lb=head(b);
	if(la!=lb)
		fish[lb]=la;
}//给没有爸爸的，给个爸爸
int main(){
	int n,m,x;
	while(cin>>n>>m){
		if(n==0&&m==0)break;
		for(int i=0;i<n;i++)fish[i]=i;
		for(int k=0;k<m;k++){
			cin>>x;mes(lv,0);
			for(int i=0;i<x;i++)cin>>lv[i];//赋值
			sort(lv,lv+x);//由小到大排序
			//for(int i=0;i<x;i++)cout<<lv[i]<<endl;
			for(int i=0;i<x-1;i++)
				cmb(lv[i],lv[i+1]);//尽量让小的是爸爸，这没啥用，你只需让所有连的连起来就行，顺序不重要
		}
		ll sum=1,flag=head(0);//定义sum,并将0的爸爸找出来
		for(int i=1;i<n;i++){
			if(head(i)==flag)sum++;//只要是和0一个爸爸，或者是0的爸爸，就加1
		}
		cout<<sum<<endl;
	} 
}

精简版：

复制代码

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<queue>
#include<vector>
#define ll long long
#define mes(x,y) memset(x,y,sizeof(x))
using namespace std;
ll fish[1000040];
int head(int p){
	if(fish[p]!=p)fish[p]=head(fish[p]);
	return fish[p];
}//搜索爸爸是哪个
void cmb(int a,int b){
	int la=head(a),lb=head(b);
	if(la!=lb)
		fish[lb]=la;
}//给没有爸爸的，给个爸爸
int main(){
	int n,m,x,y,z;
	while(cin>>n>>m){
		if(n==0&&m==0)break;
		for(int i=0;i<n;i++)fish[i]=i;
		while(m--){
			cin>>x;cin>>y;
			for(int i=1;i<x;i++){
				cin>>z;cmb(y,z);y=z;
			}//给爸爸 
		}
		int sum=1,flag=head(0);//定义sum,并将0的爸爸找出来
		for(int i=1;i<n;i++)
			if(head(i)==flag)sum++;//只要是和0一个爸爸，或者是0的爸爸，就加1
			
		cout<<sum<<endl;
	} 
}

精简2.0：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;
int tree[30001];
int head(int n) {return n == tree[n] ? n : tree[n] = head(tree[n]);}
int main() {
    int n, m, t, i, j, x, y, z, sum = 0;
    while (cin >> n >> m) {
        if (n == m && n == 0)break;
        for (i = sum = 0; i <= n; i++)tree[i] = i;
        for (i = 1; i <= m; i++) {
            cin >> t >> x;
            for (j = 2; j <= t; j++)cin >> y, tree[head(y)] = head(x);
        }
        for (i = 0, j = head(0); i <= n; i++)sum += (head(i) == j);
        cout << sum << endl;
    }
    return 0;
}