【数据结构】并查集

更新于 分类于 ， 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 1 分钟

并查集是一种对父亲节点信息有记录的数据结构，常与图论结合

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
//初始化
for(int i=1;i<=n;i++) 
    fa[i]=i;

//查找
int father(int x) {
    return fa=fa[x]==x?x:father(fa[x]);
}

//合并
void unite(int x,int y) {
    fa[father(x)]=father(y);
}

题型

  • 判断一共有几个根节点：循环一遍判断father(i) 是否等于ii

  • 特殊题型1：种类（关系）并查集：有几个种类就将数组开到几倍nn ，这样每一段nn​ 个数组表示一个种类。注意：虚拟节点和真实节点，注意合并的顺序

  • 特殊题型2：并查集删边：可离线的情况下，倒序添加边。

题目

洛谷P1892 团伙 种类并查集

洛谷P1955 程序自动分析

洛谷P3958 奶酪

洛谷P3144 Closing the Farm S 并查集删边后联通问题（离线）

洛谷P1653 并查集应用，WA40

洛谷P3144 并查集倒序加边

洛谷P1525 关押犯罪

种类并查集+贪心

NOIP2010 提高组] 关押罪犯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意

NN 个点，给出MM 对关系，即点aa 和bb 有关系值cc ，将点分为两组，使得每组中存在的点关系值的最大值最小。

N≤20000,M≤100000N\leq20000,M\leq 100000

分析

很简单的贪心，尽量拆大的关系，实在拆不了就可以输出了。分配时用并查集记录已分配的关系。

（本人oi菜鸡时期码风，见谅）

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
int fa[N];
struct node{
    int u,v,c;
}edge[M];
bool cmp(const node& a,const node& b)
{
    return a.c>b.c;
}
int father(int x)
{
    return fa[x]=(fa[x]==x)?fa[x]:father(fa[x]);
}
bool check(int x,int y)
{
    return father(x)==father(y);
}
void unite(int x,int y)
{
    fa[x]=y;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
        scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].c);
    sort(edge,edge+m,cmp);
    for(int i=1;i<=(n<<1);i++)
        fa[i]=i;
    int i=0;
    for(i=0;i<m;i++)
    {
        if(check(edge[i].u,edge[i].v)||check(edge[i].u+n,edge[i].v+n))
        {
            printf("%d",edge[i].c);
            break;
        }
        else {
            fa[father(edge[i].u)]=father(edge[i].v+n);
            fa[father(edge[i].v)]=father(edge[i].u+n);
        }
    }
    if(i==m) printf("0");
    return 0;
}