并查集

Posted on

并查集定义

​ 并查集:一种维护集合的数据结构, 可以支持两种操作

1. union: 合并两个集合
 2. find:判断两个元素是否在一个集合中

并查集的操作

并查集是由father链接构成的树

1
int father[MAX]; //每个结点保存自己的father结点的下标
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
//
void init(int n){
	for(int i=0;i<n;i++){
	father[i]=-1;//每个人都是自己的父亲,树高为1,负值表示高度
	}
}

//带路径的压缩
void Find(int x){ //Find的递归写法 
	if(Father[x]<0 ){ return x; } // x为根
	else {
			return Father[x] = Find(x); //采用路径压缩
	}
}

void Union(int a,int b){ //按秩合并
	int fa = Find(a);
    int fb = Find(b);
    if( fa!=fb) {
        if(Fathe[fa]<Father[fb}]){ //fa的树更高,fb并到fa
            Father[fb] = fa;
        }else if( Father[fa] == Father[fb]){
            Father[fb] = fa;//树高+1
            Father[fa]--;
        }else{
            Father[fa] =  fb;
        }
    }
}

相关题目:

PAT1114 Family Property

[code]:

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
const double INF = 1e-7;
int father[10001];//维护并查集
bool vis[10001];//表明那个是有效的id

int find(int x) {
    while(x != father[x])
        x = father[x];
//    father[init] = x;
    return x;
}

void Union(int a, int b){
    int fa = find(a);
    int fb = find(b);
    if(fa==fb) return;
    if(fa<fb){//a是根
        father[fb] = fa;
    }else{
        father[fa]=fb;
    }
}

//这里id就用int表示即可,方便用并查集实现
struct Node{
    int id, fid,mid,cn,estate,area;
    int cid[10];//k<5
    Node(int i, int f, int m,int cn):id(i),fid(f),mid(m),cn(cn),estate(0),area(0){
        for(int i=0;i<10;i++){
            cid[10]=0;
        }
    };
};



struct Data{
    int people;//人数
    int id;
    double estate;
    double area;
    bool flag;//表明该data是否根结点
    Data():people(0),estate(0),area(0),flag(false),id(0){};
};

bool cmp(Data a, Data b){//estate 降序
    return abs(a.area - b.area) > INF ? a.area > b.area : a.id < b.id;
}
Data roots[10000];
int main(){
    int N;
    cin>>N;
    vector<Node> nodes;
    for(int i=0;i<10001;i++){
        father[i]=i;
    }
    for(int i=0;i<N;i++){
        int id, fid,mid,cn;
        cin >> id >> fid>> mid>>cn;
        Node temp = Node(id,fid,mid,cn);
        for(int j=0;j<cn;j++){
            cin>>temp.cid[j];
        }
        cin>> temp.estate >> temp.area;
        nodes.push_back(temp);
    }//读入每个人的信息
    //进行合并
    for(int i=0;i<N;i++){
        Node temp = nodes[i];
        int  k = nodes[i].cn;
        if(temp.fid!=-1){
            Union(temp.id, temp.fid);
            vis[temp.fid] = true;
        }
        if(temp.mid!=-1){
            Union(temp.id,temp.mid);
            vis[temp.mid] = true;
        }
        for(int j=0;j<k;j++){
            Union(temp.id,temp.cid[j]);
            vis[temp.cid[j]] = true;
        }
        vis[temp.id] = true;
    }

    //统计每个家族的情况
    int count = 0;
    for(int i=0;i<N;i++){
        Node temp = nodes[i];
        int x = find(temp.id);
        roots[x].id = x ;//用于比较
        if(!roots[x].flag){
            count++;
            roots[x].flag = true;
        }
        roots[x].estate +=temp.estate;
        roots[x].area += temp.area;
    }
    for(int i=0;i<10000;i++){
        if(vis[i]){
            roots[find(i)].people++;
        }
    }
    for(int i=0;i<10000;i++){
        if(roots[i].flag){
//            cout<<roots[i].id<< " "<<roots[i].estate<< " "<<roots[i].area<<" " <<roots[i].people<<endl;
            roots[i].estate = roots[i].estate /(1.0*roots[i].people);
            roots[i].area= roots[i].area / (1.0*roots[i].people);
        }
    }
    sort(roots,roots+10000,cmp);//
    cout<<setiosflags(ios::fixed)<< setprecision(3);
    for(int i=0;i<count;i++){
        char ss[5];
        sprintf(ss,"%04d",roots[i].id);
        cout<<ss<<" "<<roots[i].people<<" "<<roots[i].estate<<" "<<roots[i].area<<endl;
    }


}