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

欢迎来玩有第三场的LABCEG 传送门

G

并查集。看到本题第一想法就是并查集，由于题目中合并两个集合的条件是两集合之间的点有边相连，那么我们考虑怎样的点，对增加集合元素有贡献。

首先已经被扫过的点显然对答案没有贡献，我们发现每次扩展出新的点可能对答案会产生贡献，我们不妨称之为可扩展点或者说是边界点。对于一个集合我们可以开一个队列保存有哪些边界点，每一次向外扩展，现当于把队列内的边界点取出往外扩展一层，并且加入的集合。我们不难发现这个过程有点类似于bfs，其实向外扩展一层现当于向外执行一层bfs，因此我们每次往外扩展时采用这种类bfs的策略来找到需要合并哪些集合。但是这题卡空间，我们无法开个，那么我们需要手写用链表实习队列。

对于集合合并我们必须保持复杂度，必须同时使用路径压缩和按秩合并。那么我们就面临一个问题：染色。我们知道在按秩合并的过程中我们无法保证某个集合的颜色为那么我们只需要开个数组或者map维护一下每个集合的颜色就行了(一开始所有集合的颜色都是自己)。

关于此题还有一个细节需要注意，对于一个集合如果其已经被一个集合合并，我们应当认为是空的，即当时该步操作我们无需执行任何操作。具体说明可以见样例解释。

#include <bits/stdc++.h>

using namespace std;

#define ll long long
ll input(){
    ll x=0,f=0;char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return f? -x:x;
}

#define pb push_back

const int N=8e5+1;

struct node{
    int w;
    node *next;
};

struct Qu{
    node *head,*end,*del;

    int front(){
        return head->w;
    }

    void push(int x){
        if(head==NULL&&end==NULL) head=end=new(node);
        else{
            end->next=new(node);
            end=end->next;
        }
        end->w=x;
    }

    void pop(){
        del=head;
        if(head==end) head=end=NULL;
        else head=head->next;
        delete(del);
    }

    bool empty(){
        return head==NULL&&end==NULL;
    }
}q[N];

int fa[N],rk[N];

int find(int x){ return fa[x]==x? x:(fa[x]=find(fa[x]));} 
void merge(int x,int y){
    x=find(x),y=find(y);

    if(x!=y){
        if(rk[x]>=rk[y]){
            while(!q[y].empty()) q[x].push(q[y].front()),q[y].pop();
            fa[y]=x,rk[x]+=rk[y];
        }else{
            while(!q[x].empty()) q[y].push(q[x].front()),q[x].pop();
            fa[x]=y,rk[y]+=rk[x];
        }
    }
}

vector <int> G[N];
Qu tmp;
map <int,int> mp;
int n,m;

void Solve(){
    n=input(),m=input();

    mp.clear();
    for(int i=1;i<=n;i++){
        while(!q[i].empty()) q[i].pop();q[i].push(i);
        rk[i]=1,fa[i]=i;G[i].clear();
        mp[i]=i;
    }


    for(int i=1;i<=m;i++){
        int u=input()+1,v=input()+1;
        G[u].pb(v),G[v].pb(u);
    }

    int QQ=input();
    for(int i=1;i<=QQ;i++){
        while(!tmp.empty()) tmp.pop();
        int u=input()+1,tu;
        tu=u;
        if(u!=mp[find(u)]) continue;
        u=find(u);
        while(!q[u].empty()) tmp.push(q[u].front()),q[u].pop();
        // cout<<i<<":"<<tmp.front()<<endl;
        while(!tmp.empty()){
            int t=tmp.front();tmp.pop();
            for(auto v:G[t]){
                merge(v,t);
            }
        }

        mp[find(u)]=tu;
    }

    for(int i=1;i<=n;i++){
        printf("%d%c",mp[find(i)]-1,i==n? '\n':' ');
    }
}

int main(){
    int T=input();
    while(T--)
        Solve();
}