思路：首先想到暴力做法，每次将 其他点并到节点 (a) 时，删掉 (a) 现有的连边并将新加入的 (group) 中的点连出去的所有边连到 (a) 上，并将的这些节点的父亲设为 a,
每次都这么操作，是能保证可以得出正确结果的，但是一定会 (tle) ，维护父亲节点我们可以用并查集，但是将新加入的 (group) 中的点连出去的所有边连到 (a) 上相当于复制所有边，这样操作的复杂度会很高，其实我们可以不用复制所有边，如果你前向星见图掌握的好的话，我们其实可以发现，一个点的所有边可 以用一个序列表示出来，(head[u]) 就是这个序列的第一个点，我们再维护一下这个序列时什么时候结束的，每次要将新节点的边复制到节点 (a) 时，我们可以 将这些新节点的边序列连起来，具体怎么连看代码， 再让 (head[a]) 等于这个序列的起点，这样的复杂度就会低很多，粗略的算了一下，大概是 (o(2 imes m)) 的复杂度，因为每条边只会被遍历一次，加上建图的时候的反边，就是 (o(2 imes m)) ， 至于父节点可以用并查集维护。
详细请看以下代码
#include <cstdio>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
#include <string.h>
#include <map>
#include <iostream>
using namespace std;
const int maxn = 2e6 + 50;
const int mod = 20090717;
typedef long long LL;
int INF = 1e9;
typedef pair<int, int> pii;
#define fi first
#define se second
int fa[maxn]; // 并查集
int Find(int x){
if(fa[x] == x){
return x;
}
return fa[x] = Find(fa[x]);
}
void unit(int x, int y){
x = Find(x), y = Find(y);
if(x == y) return ;
fa[y] = x;
}
struct Edge
{
int to, next;
} edge[maxn * 2];
int k, head[maxn];
int sid[maxn], eid[maxn]; // 记录一个节点的起始边和终止边
void add(int a, int b){
edge[k].to = b;
edge[k].next = head[a];
if(eid[a] == -1) sid[a] = eid[a] = k;
else sid[a] = k;
head[a] = k++;
}
int vis[maxn];
queue<int> que;
int main(int argc, char const *argv[])
{
int t;
scanf("%d", &t);
while(t--){
k = 0;
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i <= n; i++){
head[i] = -1;
vis[i] = 0, fa[i] = i;
sid[i] = eid[i] = -1;
}
for(int i = 1; i <= m; i++){
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
add(b, a);
}
int q;
scanf("%d", &q);
while(q--){
int u;
scanf("%d", &u);
if(vis[u]) continue;
for(int i = head[u]; i != -1; i = edge[i].next){
int to = edge[i].to;
to = Find(to);
if(to == u) continue;
unit(u, to);
vis[to] = 1; // group[to] 为空，标记一下
que.push(to); // 存一下新加入的点
}
int fg = 1;
head[u] = -1; // 这句要记得加上，因为如果已经没有点可以并到group上，那么head[u]不会更新，之后每次操作u都会遍历最后一次连在u上的点，会导致tle
while(que.size()){
int to = que.front();
que.pop();
if(fg) {
fg = 0;
sid[u] = sid[to]; // 记录新的起点
head[u] = sid[to];
} else {
edge[eid[u]].next = sid[to]; // 将不同的两个点的边序列链接
}
eid[u] = eid[to]; // 记录终点
}
}
for(int i = 0; i < n; i++){
Find(i);
printf("%d ", fa[i]);
}
printf("
");
}
return 0;
}