查并集Disjoint Set（不相交的集合）_两个不相交的集合的并集

学习篇+板子

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

实现方法一（常用）： 每个集合用一棵“有根树”表示
1、定义数组Set[1,n];
2、Set[ i ] = i ;则 i 表示本集合，并使集合对应树的根
3、Set[ i ] = j ;若 j 不等于 i ，则 j 是 i 的父节点

举个例子：

具体操作：
1、查：最坏情况O（n）

findx(x){
    while(x!=Set[x])x=Set[x];//找父节点“找领导”
    return x;
}
1
2
3
4

2、并：O（1）

mergeset(a,b){//a,b都是根节点（他俩是各自的领导）
	Set[a]=b;//表示把a的领导换成了b；
}
1
2
3

避免最坏的情况：（一般不需要）
方法：将深度小的树合并到深度大的树上（深度是要另外用数组计数的）
效果：任意顺序合并后，包含k个节点的树的最大高度不超过 lg（k）；
1、查：

findx(x){
    while(x!=Set[x])x=Set[x];//找父节点“找领导”
    return x;
}
1
2
3
4

2、并：

mergeset(a,b){//a,b都是根节点（他俩是各自的领导）
	if(h[a]==h[b]){
		h[a]++;
		Set[b]=a;
	}
	else if(h[a] <h[b])Set[a]=b;
	else Set[b]=a;
}
1
2
3
4
5
6
7
8

实现方法二（不常用）：
1、用编号最小的元素标记所在集合；
2、定义一个数组Set[1,n],其中Set[i]表示元素i所在的集合；

举个例子：

则不相交集合：
{1，3，7}，{4}，{2，5，9，10}，{6，8}
课件每个不相交集合的第一个元素所对应的Set(0)就为该集合中所有元素所对应的值

具体操作：
1、查：O（1）

findx(x){return Set[x];}
1

2、合并：O（n）

mergeset(a,b){
    i=min(a,b);
    j=max(a,b);
    for(k=1;k<=n;k++){
       if(Set[k]==j)Set[k]=i;
    }
}
1
2
3
4
5
6
7

并集的简单应用
1、最小生成树

水题集

hdu 1232：求至少还需要建多少条路使城市互通

hdu 1233

题意：给出互通的两个城市的编号，使全省任意两个城市互通，最少还需要建设多少条道路。
典型的查并集问题

#include <bits/stdc++.h>
#define ll long long

using namespace std;
int s[1010];

int findx(int x){
    int r=x;
    while(s[r]!=r)r=s[r];
    return r;
}

void mergeset(int a,int b){
    int x=findx(a);
    int y=findx(b);
    if(x!=y)s[y]=x;//初次尝试查并集：注意这个地方一定是根节点换，第一次写成s[b]=a，错误
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m;
    while(scanf("%d",&n),n){
        for(int i=1;i<=n;i++)s[i]=i;
        for(scanf("%d",&m);m>0;m--){
            int a,b;scanf("%d%d",&a,&b);
            mergeset(a,b);
        }
        int ans=-1;
        for(int i=1;i<=n;i++){
            if(s[i]==i)ans++;
        }
        printf("%d\n",ans);
    }
    return 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

hdu 1233：最小生成树

HDU 1233
典型的最小生成树-[查并集的简单应用]

题中的：得到的统计表中列出了任意两村庄间的距离
说明了给的数据一定能形成最小生成树

#include <bits/stdc++.h>
#define ll long long

using namespace std;

//最小生成树问题
int s[110];

struct node {int a, b, d;}c[5000];
bool cmp(node x,node y){return x.d<y.d;}

int findx(int x){//查并集中的查
    while(x!=s[x])x=s[x];
    return x;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    while(scanf("%d",&n),n){
        int m=n*(n-1)/2;
        for(int i=1;i<=m;i++)scanf("%d%d%d",&c[i].a,&c[i].b,&c[i].d);
        sort(c+1,c+1+m,cmp);//排序；将边的权值从小到大排序；
        for(int i=1;i<=n;i++)s[i]=i;//查并集一定的步骤：“根的初始化”
        
        int ans=0,g=0;
        for(int i=1;i<=m;i++){
            if(findx(c[i].a) !=findx(c[i].b) ){//只有根节点不同才能进行；否则就不是树就成环了
                ans+=c[i].d;
                s[ findx(c[i].a) ]=findx(c[i].b);//合并
                g++;if(g==n-1)break;//这一步可有可无；这一步剪枝；因为是树所以就是n-1条边；
            }
        }
        printf("%d\n",ans);
    }
    return 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

此链接：别人的题解，加了个ran数组 记录深度 优化查并集，但是这给题n<100没必要加，可以学习一下别人记录深度的做法

hdu 1863：最小生成树及其能否构成的判断

HDU 1863

题中的：统计表中列出了有可能建设公路的若干条道路的成本
说明了不一定能形成最小生成树（即不能畅通输出 “？”），且 m<= sum(1+2+```+n-1)=n*n/2=5000;
不能生成最小数的判断有两个方法：

法一：
遍历每个根节点出现不同则不能生成：有两种实现方式

方式①：

#include <bits/stdc++.h>
#define ll long long

using namespace std;

//最小生成树问题
int s[110];

struct node {int a, b, d;}c[5010];
bool cmp(node x,node y){return x.d<y.d;}

int findx(int x){
    while(x!=s[x])x=s[x];
    return x;
}

int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)){
        if(n==0)break;
        //if(n<m-1){printf("?\n");continue;}第一次写加了这句话直接就tle了？？？
        for(int i=1;i<=n;i++)scanf("%d%d%d",&c[i].a,&c[i].b,&c[i].d);

        for(int i=1;i<=m;i++)s[i]=i;
        sort(c+1,c+1+n,cmp);
        int ans=0,g=0,cnt=0;
        for(int i=1;i<=n;i++){
            if(findx(c[i].a) !=findx(c[i].b) ){
                ans+=c[i].d;
                s[ findx(c[i].a)]=findx(c[i].b);
                g++;if(g==m-1)break;
            }
        }
        bool f=0;
        for(int i=2;i<=m;i++){
            if(findx(1)!=findx(i)){f=1;break;}//判断根节点是否都相同
        }
        if(f)printf("?\n");
        else printf("%d\n",ans);
    }
    return 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

方式②：

#include <bits/stdc++.h>
#define ll long long

using namespace std;

//最小生成树问题
int s[110];

struct node {int a, b, d;}c[5010];
bool cmp(node x,node y){return x.d<y.d;}

int findx(int x){
    while(x!=s[x])x=s[x];
    return x;
}

int main(){
    int n,m;
    while(scanf("%d%d",&n,&m),n){
        for(int i=1;i<=n;i++)scanf("%d%d%d",&c[i].a,&c[i].b,&c[i].d);

        for(int i=1;i<=m;i++)s[i]=i;
        sort(c+1,c+1+n,cmp);
        int ans=0,g=0,cnt=0;
        for(int i=1;i<=n;i++){
            if(findx(c[i].a) !=findx(c[i].b) ){
                ans+=c[i].d;
                s[ findx(c[i].a)]=findx(c[i].b);
                g++;if(g==m-1)break;
            }
        }
        for(int i=1;i<=m;i++){
            if(s[i]==i)cnt++;//cnt计数有多少个根节点
        }
        if(cnt==1)printf("%d\n",ans);
        else printf("?\n");
    }
    return 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

法二：搜完那些数据以后，能构成的边小于m-1

#include <bits/stdc++.h>
#define ll long long

using namespace std;

//最小生成树问题
int s[110];

struct node {int a, b, d;}c[5010];
bool cmp(node x,node y){return x.d<y.d;}

int findx(int x){
	while(x!=s[x])x=s[x];
	return x;
}

int main(){
	int n,m;
	while(scanf("%d%d",&n,&m)){
		if(n==0)break;

		for(int i=1;i<=n;i++)scanf("%d%d%d",&c[i].a,&c[i].b,&c[i].d);

		for(int i=1;i<=m;i++)s[i]=i;
		sort(c+1,c+1+n,cmp);
		int ans=0,g=0,cnt=0;
		for(int i=1;i<=n;i++){
			if(findx(c[i].a) !=findx(c[i].b) ){
				ans+=c[i].d;
				s[ findx(c[i].a)]=findx(c[i].b);
				g++;if(g==m-1)break;
			}
		}
		if(g<m-1)printf("?\n");
		else printf("%d\n",ans);
	}
	return 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

wa了好多次

hdu 1272：小希的迷宫

HDU 1272

题意：构成一个“联通的图”且不能有环

wa了好多发的原因：
1、我以为这个题仅仅只是没有环，直接找两点的根是否相同就行，但是！！！没注意到是构成一个图，也就是说，还得判断根有几个
2、输入是0 0的时要输出yes
3、输出的yes和no的大小写，最后几发被这个贡献了他竟然不是PE。

#include <bits/stdc++.h>
using namespace std;

int s[100010],v[100010];

int findx(int x){
    while(x!=s[x])x=s[x];
    return x;
}

int main(){
    int a,b;
    while(scanf("%d%d",&a,&b)){
        if(a==-1&&b==-1)break;
        if(a==0&&b==0){printf("Yes\n");continue;}
        
        for(int i=1;i<=100000;i++){s[i]=i;v[i]=0;}
        
        v[a]=1;v[b]=1;s[a]=b;
        int x,y,cnt=0,g=0;bool f=0;
        while(scanf("%d%d",&x,&y)){
            if(x==0&&y==0)break;
            v[x]=1;v[y]=1;
            if(findx(x)==findx(y))f=1;//判断是否形成环
            s[findx(x)]=findx(y);
        }
        if(f)printf("No\n");
        else {//判断形成多少个图
            for(int i=1;i<=100000;i++){
                if(v[i] && s[i]==i)g++;
            }
            if(g==1)printf("Yes\n");
            else printf("No\n");
        }
    }
    return 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