并查集

poj2524

一个基础的并查集问题，n个人，每个人只能有一个信仰，每次给出两个人相同信仰的编号(编号从1到n),一共m次，问一共有多少种信仰。

#include <iostream>
typedef long long ll;
const ll N = 5e4+7;
using namespace std;
ll fa[N];
int n, m;
void init(){
    for (int i = 1; i <= n; i++)
        fa[i] = i;
}
int find(int x){ //查找
    return x == fa[x] ? x : fa[x]=find(fa[x]);
}
void mergeset(int x, int y){//合并
    fa[find(x)]=find(y);
}
int main()
{
    int cnt=1;
    while (cin >> n >> m)
    {
        if(n == 0 && m==0) break;
        init();
        for (int i = 1; i <= m; i++){
            int x, y;
            cin >> x >> y;
            mergeset(x , y);
        }
        ll ans = 0;
        for (int i = 1; i <= n; i++)
        {
            if (fa[i] == i)
                ans++;
        }
        cout<<"Case "<<cnt++<<": "<<ans<<endl;
    }

    return 0;
}

查找与0同一组的数目

poj1611

#include <iostream>
typedef long long ll;
const ll N = 3e4 + 7;
using namespace std;
ll fa[N];
int n, m;
void init()
{
    for (int i = 0; i <= n - 1; i++)
        fa[i] = i;
}
int find(int x)
{ //查找
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void mergeset(int x, int y)
{ //合并
    x=find(x),y=find(y);
    if(x==0) fa[y]=0;
    else fa[x]=y;
}   
int main()
{
    int cnt = 1;
    while (cin >> n >> m)
    {
        int x,y,k;
        if (n == 0 && m == 0)
            break;
        init();
        while (m--)
        {
            cin>>k;
            cin >> x;
            for (int i = 2; i <= k; i++)
            {
                cin >> y;
                mergeset(x, y);
                x = y;
            }
        }

        ll ans = 0;
        for (int i = 0; i <= n-1; i++)
        {
            if (find(i) == 0)
                ans++;
        }
        cout <<ans<< endl;
    }

    return 0;
}

poj1703

题意：给你n个人，这n个人只属于两个不同的团体，m次操作

A x y:询问x,y是否是在一个团体
D x y:x,y不是一个团体

解法：一共有n个人，x,y不是一个团体，可以看成x与y的对立面是一个团体的，因此可以用一个2n的数组来存这个关系，接下来就是普通的并查集即可。

#include <iostream>
#include<cstdio>
typedef long long ll;
const ll N = 1e5 + 7;
using namespace std;
ll fa[N << 1];
int n, m;
void init()
{
    for (int i = 1; i <= n * 2; i++)
        fa[i] = i;
}
int find(int x)
{ //查找
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void mergeset(int x, int y)
{ //合并
    fa[find(x)] = find(y);
}
int main()
{
    int cnt = 1;
    int t;
    cin>>t;
    while (t--){
        scanf("%d%d",&n,&m);
        int x, y;
        char  op;
        init();
            for (int i = 1; i <= m; i++){
                scanf(" %c%d%d",&op,&x,&y);
                if(op=='D'){
                    mergeset(x,y+n);
                    mergeset(x+n,y);
                }
                else{
                    if(find(x) == find(y+n)){
                        printf("In different gangs.\n");
                    }
                    else if(find(x) == find(y)){
                        printf("In the same gang.\n");
                    }
                    else printf("Not sure yet.\n");
                }
            }
    }
    return 0;
}

B 经商

题意：

给你n个人，以及他们之间的联系。已知1号的精力，1号要去和其他人员交易，交易要花费精力，同时会获得收益，让你求怎么样才能获得最大收益。

题解：

其实这道题就是一个背包加并查集，先用并查集求出他们之间的关系，然后直接背包就行了，记得在dp的时候判断他们之间是否有关系，有关系才能装进去。

#include <bits/stdc++.h>
typedef long long ll;
const ll N = 1e5 + 7;
using namespace std;
ll fa[N],dp[N],a[N],b[N];
int n, m,k;
void init()
{
    for (int i = 1; i <= n; i++)
        fa[i] = i;
}
int find(int x)
{ //查找
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void mergeset(int x, int y)
{ //合并
    fa[find(x)] = find(y);
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        scanf("%d%d%d", &n, &m, &k);
        int x, y;
        init();
        for(int i = 2; i <= n;i++){
            cin>>a[i]>>b[i];
        }
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d", &x, &y);
            mergeset(x, y);
        }
        memset(dp,0,sizeof(dp));
        for(int i=2;i<=n;i++){
                for(int j=k;j>=a[i];j--){
                     if(find(i) == find(1)){
                        dp[j] = max(dp[j] , dp[j-a[i]]+b[i]);
                    }
            }
        }
        cout<<dp[k]<<endl;
    }

    return 0;
}