2020牛客暑期多校训练营（第三场）G

Description

给定一个 (n) 个点的图，第 (i) 个点一开始是第 (i) 种颜色，接着有 (k) 次操作，第 (i) 次操作指定一个点 (o_i)，表示第 (o_i) 种颜色会侵略所有与自己相邻的颜色，求最终每个点的颜色。

Solution

任意时刻，每种颜色唯一对应一个连通块

考虑用并查集维护连通块，其根结点表示颜色

则只有 (o_i) 是根结点时才可以向外侵略，对于到达的每一个新连通块，将它整个挂在 (o_i) 下即可

对每个连通块，维护一个生长结点集合，表示从这个连通块一步扩展可以到达的可能属于新连通块的点

初态下每个连通块的生长结点集合就是它的邻接点

每次将所有连通块 (q) 并入连通块 (p) 时，(p) 原有的生长结点集合会被丢掉（本次遍历了），新的生长结点集合将由所有的 (q) 的生长结点集合合并而成

这个过程可以用 vector 启发式合并，也可以用 list.splice 做到线性时间复杂度

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int N = 1000005;

int t,t1,t2,q,x,n,m,fa[N];
list<int> g[N];

signed main()
{
    function<int(int)> find=[&](int x) {return fa[x]==x ? x : fa[x]=find(fa[x]);};

    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=0;i<n;i++)
        {
            g[i].clear();
            fa[i]=i;
        }
        for(int i=1;i<=m;i++)
        {
            cin>>t1>>t2;
            g[t1].pb(t2);
            g[t2].pb(t1);
        }
        cin>>q;
        while(q--)
        {
            cin>>x;
            int fx=find(x);
            if(x==fx)
            {
                list<int> res;
                for(auto i:g[fx])
                {
                    int q=find(i);
                    if(q!=fx)
                    {
                        fa[q]=fx;
                        res.splice(res.end(), g[q]);
                    }
                }
                swap(res, g[fx]);
            }
        }
        for(int i=0;i<n;i++) cout<<find(i)<<" ";
        cout<<endl;
    }
}