专题四 并查集&生成树

并查集&生成树

[题目][A]

How Many Tables

题目大意：

有T个(1 <= T <= 25)个测试样例，每个测试样例中有一个n,m(1 <= n,m <= 1000)，表示有n个人(编号1到n)，然后下面m行表示，a和b认识。只有相互认识的人(直接或间接)才能坐一桌，最后输出最少需要坐多少张桌子。

解题思路：

对于每个测试样例，根据m行表示朋友关系的a,b，进行并查集合并，然后看有多少个不同的集合，也就是最少的桌子数。
时间复杂度O(T*(n+m)),空间复杂度O(n).

AC代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int maxn = 1003;
int pre[maxn];
int root[maxn];
int Find(int x)
{
    int r = x;
    while(r != pre[r]) r = pre[r];
    int i = x,j;
    while(pre[i] != r)
    {
        j = pre[i];
        pre[i] = r;
        i = j;
    }
    return r;
}
void mix(int a,int b)
{
    int fa = Find(a),fb = Find(b);
    if(fa != fb)
    {
        pre[fb] = fa;
    }
}
int main()
{
    int t;
    int i;
    int n,m;
    int a,b;
    int ans;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i = 1;i <= n;i++)
            pre[i] = i;
        for(i = 1;i <= m;i++)
        {
            scanf("%d%d",&a,&b);
            mix(a,b);
        }
        memset(root,0,sizeof(root));
        for(i = 1;i <= n;i++)
        {
            root[Find(i)] = 1;
        }
        for(ans = 0,i = 1;i <= n;i++)
        {
            if(root[i]) ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

[题目][B]

Corporative Network

题目大意：

测试样例有T个。
有N个点(5 <= N <= 20000),执行如下3种指令：
E m：  输出m到根的距离(m到根中，每一段距离之和)
I a b: a接到b上，即a的前驱变为b。
O：    指令执行结束。

解题思路：

并查集。按顺序执行指令(x个(x <= 200000 ))，执行E时，就查找m，然后输出dis[m]，并且进行路径压缩，同时修改m的前驱为根，并且更新这条路径上的点到根的距离。执行I时，把a的前驱改为b，并且修改ab之间的距离为|a-b|%1000。
时间复杂度O(t*(n+x)),空间复杂度O(n).

AC代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 20000+5;
int dis[maxn];
int root[maxn];
int n;
void init()
{
    int i;
    for(i = 1;i <= n;i++)
    {
        dis[i] = 0;
        root[i] = i;
    }
}
int findr(int m)
{
    int x;
    if(root[m] == m) return m;
    x = root[m];
    root[m] = findr(root[m]);
    dis[m] += dis[x];
    return root[m];
}
int main()
{
    int t;
    char ch;
    int a,b;
    int m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        init();
        while(scanf("%c",&ch) && ch != 'O')
        {
            if(ch == 'E')
            {
                scanf("%d",&m);
                findr(m);
                printf("%d\n",dis[m]);
            }
            if(ch == 'I')
            {
                scanf("%d%d",&a,&b);
                root[a] = b;
                dis[a] = abs(a-b)%1000;
            }
        }
    }
    return 0;
}