CQUPT 集训队专题训练（并查集/生成树）

并查集/生成树

并查集
并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。
需要实现的操作有：合并两个集合，判断两个元素是否属于一个集合。
这里介绍的主要是普通的并查集，很多情况下使用的并查集是需要扩展的，根据使用情况的不同，有很多差别，这里仅仅是最基本的算法。

最小生成树
给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树.
Kruskal算法 克鲁斯卡尔算法
方法:将图中边按其权值由小到大的次序顺序选取,若选边后不形成回路,则保留作为一条边,若形成回路则除去.依次选够(n-1)条边,即得最小生成树.(n为顶点数)
普里姆算法
方法:从指定顶点开始将它加入集合中,然后将集合内的顶点与集合外的顶点所构成的所有边中选取权值最小的一条边作为生成树的边,并将集合外的那个顶点加入到集合中,表示该顶点已连通.再用集合内的顶点与集合外的顶点构成的边中找最小的边,并将相应的顶点加入集合中,如此下去直到全部顶点都加入到集合中,即得最小生成树.

A - How Many Tables
题意：

Ignatius有N个朋友，朋友不是相互认识，A认识B，B认识C则ABC相互认识并可以坐在一起吃饭（同一张桌子），有M中关系，(1<=N,M<=1000)，求至少需要多少张桌子

解题思路：

并查集，有多少个父亲节点就需要多少张桌子。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int fa[1024];
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,m,a,b;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        fa[i]=i;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            int tmp;
            int x=find(a);
            int y=find(b);
            if(x>y)
            {
                tmp=x;
                x=y;
                y=tmp;
            }
            if(x!=y)
            {
                fa[y]=x;
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            if(fa[i]==i)
            ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

B - Corporative Network
题意：

N个公司，I公司与公司之间的距离是|I – J|(mod 1000)，有三种操作
1.E I 指的是连接到I公司的其他公司服务器的距离之和
2.I I J 将J公司的服务器连接到I公司
3.O 结束操作

解题思路：

连接两个节点时，将J作为I的父亲节点，|I-J|%1000求出IJ之间距离，在查找当前节点的根节点时，一边维护当前节点到根节点的距离.

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int fa[20010],dis[20010];
int find(int x)
{
    if(x!=fa[x])
    {
        int root=find(fa[x]);
        dis[x]+=dis[fa[x]];
        return fa[x]=root;
    }
    else
    return x;
}
int abs(int x)
{
    if(x<0)
    return -x;
    else
    return x;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,i,j;
        char ss[10];
        scanf("%d",&n);
        for(int k=0;k<=n;k++)
        {
            fa[k]=k;
            dis[k]=0;
        }
        while(scanf("%s",ss)&&ss[0]!='O')
        {
            if(ss[0]=='E')
            {
                scanf("%d",&i);
                find(i);
                printf("%d\n",dis[i]);
            }
            if(ss[0]=='I')
            {
                scanf("%d%d",&i,&j);
                fa[i]=j;
                dis[i]=abs(i-j)%1000;
            }
        }
    }
    return 0;
}

C - 卿学姐与诡异村庄
题意：

村庄总共有N（1≤N≤100000）个人，N个人相互指控，好人只会说真话，坏人只会说假话。输出N行，ai,t，如果t是1，那么说明第i个人认为第ai个人是好人。如果t是2，那么说明第i个人认为第ai个人是坏人。判断从这些人的指控中，满足一种分类每个人指控谁是否为好人

解题思路：

A说B是好人，那么可能有两种情况，若A是坏人，B也是坏人，若A是好人，B是好人
A说B是坏人，若A是好人，B是坏人，若A是坏人，B就是好人。
前（0，N）表示好人，(N,2*N）表示坏人，并查集查找此人为好人时和坏人坏人的父节点是否相同，若相同则不满足

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define hh 100000
using namespace std;
int fa[2*hh+10];
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void solve(int x,int y)
{
    int xx=find(x);
    int yy=find(y);
    if(xx!=yy)
    {
        fa[xx]=yy;
    }
}
int main()
{
    int n,a,t;
    scanf("%d",&n);
    for(int i=1;i<=hh*2+9;i++)
    {
        fa[i]=i;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a,&t);
        if(t==1)
        {
            solve(i,a);
            solve(i+hh,a+hh);
        }
        else
        {
            solve(i+hh,a);
            solve(i,a+hh);
        }
    }
    for(int i=1;i<n;i++)
    {
        if(find(i)==find(i+hh))
        {
            printf("One face meng bi\n");
        }
    }
    printf("Time to show my power\n");
    return 0;
}

D - 食物链
题意：

根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。
若D=1，则表示X和Y是同类。 
若D=2，则表示X吃Y。
判断假话的数目

解题思路：

带权并查集和普通并查集最大的区别在于带权并查集合并的是可以推算关系的点的集合（可以通过集合中的一个已知值推算这个集合中其他元素的值）。而一般并查集合并的意图在于这个元素属于这个集合。带权并查集相当于把“属于”的定义拓展了一下，拓展为有关系的集合。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int f[50005],rank[50005];
int find(int x)
{
    if(x!=f[x])  
    {  
        int fx=find(f[x]);  
        rank[x]=(rank[x]+rank[f[x]])%3;    
        f[x]=fx;  
    }  
    return f[x]; 
}
int Union(int x,int y,int d)  
{   
    int a=find(x);  
    int b=find(y);  
    if(a==b)  
    {  
        if((rank[y]-rank[x]+3)%3!=d) 
        return true;     
        else 
        return false;  
    }  
    f[b]=a;  
    rank[b]=(rank[x]-rank[y]+d+3)%3;    
    return false;  
}  
int main()
{
    int n,m;
    int d,x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
        rank[i]=0;
    }
    int ans=0;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&d,&x,&y);
        if(x>n||y>n||d==2&&x==y)
        ans++;
        else if(Union(x,y,d-1))
        {
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
 } 

E - Dark roads
最小生成树 kruskal算法
题意：

m个节点，n条路，1 ≤ m ≤ 200000，m − 1 ≤n≤200000.第i条路在x,y之间长度为z.保证联通的情况下，去掉一些边，求删去边的权值最大

解题思路：

求出边的权值的总和减去最小生成树的权值之和（最小生成树将每个点联通，并且保证权值之和最小），相减之后得到的值为所要删去边的和的最大值，

代码：
```

include

include

include

include

using namespace std;
int p[200005],r[200005];
struct Node
{
int p1,p2;
int w;
}edge[200005];
bool cmp(Node x,Node y)
{
return x.w }
int find(int x)
{
return p[x]==x?x:p[x]=find(p[x]);
}
void un( int a, int b )
{
if ( r[a] < r[b] )
p[a] = b;
else {
if( r[a] == r[b] )
r[a] ++;
p[b] = a;
}
}
int kruskal(int n,int m)
{
for(int i=0;i<=n;i++)
p[i]=i;
for(int i=0;i<=n;i++)
r[i]=0;
sort( edge, edge+m, cmp );
long long sum = 0;
for ( int i = 0 ; i < m ; ++ i ) {
int A = find( edge[i].p1 );
int B = find( edge[i].p2 );
if ( A != B ) {
un( A, B );
sum += edge[i].w;
}
}
return sum;

}
int main()
{
int n,m,a,b,c;
while(scanf("%d%d",&n,&m)&&m+n)
{
long long sum=0;
for(int i=0;i {
scanf("%d%d%d",&a,&b,&c);
edge[i].p1=a;
edge[i].p2=b;
edge[i].w=c;
sum+=c;
}
printf("%lld\n",sum-kruskal(n,m));
}
return 0;
}
```