牛客多校第三场 G. Operating on a Graph（并查集，链表）

题意：
有n个group，每个group都初始只有一个点
m次询问，每次询问给出一个group，则这个group里面点所连的点连在这个group上。
问最后每个点属于哪个group

思路：
一个点通过邻接边连接其他点称为发挥作用，则每个点最多只会发挥一次作用，所以只需要维护每个group里面还有多少没有发挥作用的点即可。

维护group可以用并查集，维护多少没发挥作用点可以用链表合并。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <list>

using namespace std;

const int maxn = 1e6 + 7;

vector<int>G[maxn];
int vis[maxn];
int fa[maxn];
int l[maxn];
int head[maxn],tail[maxn],nex[maxn],to[maxn],tot;

int findset(int x) {
    if(fa[x] == x) return x;
    return fa[x] = findset(fa[x]);
}

bool Union(int x,int y) {
    int rx = findset(x),ry = findset(y);
    if(rx != ry) {
        fa[rx] = ry;
        return true;
    }
    return false;
}

void add(int x,int y) { //y加入到group x里面
    to[++tot] = y;
    nex[tot] = head[x];
    tail[x] = tot;
    head[x] = tot;
}

void link(int x,int y) { //y对应的group 加入group x后面
    if(head[x] == 0) {
        head[x] = head[y];
        tail[x] = tail[y];
    } else {
        nex[tail[x]] = head[y];
        tail[x] = tail[y];
    }
    head[y] = tail[y] = 0;
}

int main() {
    int T;scanf("%d",&T);
    while(T--) {
        int n,m;scanf("%d%d",&n,&m);
        tot = 0;
        for(int i = 0;i < n;i++) {
            G[i].clear();
            fa[i] = i;
            tail[i] = tail[i + n] = head[i] = head[i + n] = 0;
        }
        for(int i = 0;i < n;i++) {
            add(i,i);
        }
        for(int i = 1;i <= m;i++) {
            int x,y;scanf("%d%d",&x,&y);
            G[x].push_back(y);G[y].push_back(x);
        }
        int q;scanf("%d",&q);
        while(q--) {
            int x;scanf("%d",&x);
            if(head[x] == 0) continue;
            vector<int>tmp;
    
            for(int i = head[x];i;i = nex[i]) {
                int y = to[i];
                if(findset(y) != x) continue;
                for(int j = 0;j < G[y].size();j++) {
                    int v = G[y][j];
                    int f = findset(v);
                    if(Union(v,x)) {
                        tmp.push_back(f);
                    }
                }
            }
            head[x] = tail[x] = 0;
            for(int i = 0;i < tmp.size();i++) {
                int v = tmp[i];
                link(x,v);
            }
        }
        for(int i = 0;i < n;i++) {
            printf("%d ",findset(i));
        }
        printf("\n");
    }
    return 0;
}