并查集与生成树专题

集训队

A - How Many Tables （hdu 1213）

确定人之间的关系，然后在一起♂，确定有多少组人一起♂

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int par[1005];
int n, m, t;
void init()
{
    for (int i = 1; i <= n; i++)
        par[i] = i;
}
int find(int x)
{
    if (par[x] == x)
        return x;
    else
        return par[x] = find(par[x]);
}
int main()
{
    cin >> t;
    while (t--)
    {
        int a, b, ans = 0;
        cin >> n >> m;
        init();
        for (int i = 1; i <= m; i++)
        {
            int x, y;
            cin >> a >> b;
            x = find(a);
            y = find(b);
            if(x!=y)
            par[x] = y;
        }
        for (int i = 1; i <= n; i++)
            if (par[i] == i)
                ans++;
        cout << ans << endl;
    }
    return 0;
}

B - Corporative Network poj1962

典型的带权并查集，I 连接2点，E确定此点离最终点距离（若无指向则为本身）

#include <cstdio>
#include <cstring>
#include <algorithm>    
const int maxn = 1e5;
int par[maxn], d[maxn];
int find(int x)
{
    if (par[x] == x)
        return x;
    else {
        int temp = par[x];
        par[x] = find(par[x]);
        d[x] += d[temp];
        return par[x];
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, a, b;
        char ch;
        scanf("%d", &n);
        for (int i = 0; i <= n; i++) 
        {
            par[i] = i;
            d[i] = 0;
        }
        while (scanf(" %c",&ch),ch!='O')
        {
            if (ch == 'I')
            {
                scanf("%d %d", &a, &b);
                par[a] = b; 
                d[a] = abs(a - b) % 1000;
            }
            else {
                    scanf("%d", &a);
                    find(a);
                    printf("%d\n", d[a]);
            }
        }
    }
    return 0;
}