2020牛客多校第3场 G. Operating on a Graph【并查集/链表合并】

题目描述

给出一个 个点 条边的无向图，点的编号为 ~ ，起初每个点 属于编号为 的集合
共进行 次操作，每次操作给出一个
如果没有点在编号为 的集合中，那么无事发生
否则把和编号为 的集合相邻的集合全部并入编号为 的集合
最后求每个点所在的集合编号

输入样例

1
4 3
0 1
1 2
2 3
4
0 1 3 0

输出样例

0 0 0 0

并查集 链表合并

使用存了尾节点下标的邻接表存图

每次合并集合的时候把要合并进来的那些点的邻接表连到根节点上

遍历过的边要清空一下，否则菊花图biss

时间复杂度

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 800010, M = N << 1;

int h[N], t[N], e[M], ne[M], idx;
void add(int a, int b)
{
    if(t[a] == -1)  t[a] = idx;
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int p[N];
int find(int x)
{
    if(p[x] != x)  p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int _;
    scanf("%d", &_);
    while(_ --)
    {
        int n, m;
        scanf("%d%d", &n, &m);

        idx = 0;
        for(int i = 0; i < n; i ++)  h[i] = t[i] = -1, p[i] = i;

        while(m --)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            add(a, b), add(b, a);
        }

        scanf("%d", &m);
        while(m --)
        {
            int u;
            scanf("%d", &u);
            if(p[u] != u)  continue;

            vector<int> points;
            for(int i = h[u]; ~i; i = ne[i])
            {
                int j = find(e[i]);
                if(j == u)  continue;

                p[j] = u;
                points.push_back(j);
            }

            h[u] = t[u] = -1;
            for(int j : points)
            {
                if(h[u] == -1)
                {
                    h[u] = h[j];
                    t[u] = t[j];
                }
                else
                {
                    ne[t[u]] = h[j];
                    t[u] = t[j];
                }
            }
        }
        for(int i = 0; i < n; i ++)  printf("%d ", find(i));  puts("");
    }
    return 0;
}