#include <bits/stdc++.h> using namespace std; const int maxn = 8e5+10,maxm = 8e5+10; struct edge{ int to,nxt; }e[maxm*2]; int head[maxn],h[maxn],nxt[maxn],ans[maxn],parent[maxn],cnt,n,m; void addEdge(int u,int v){ e[cnt].to = v; e[cnt].nxt = head[u]; head[u] = cnt++; } int find(int x){ return x==parent[x]?x:parent[x] = find(parent[x]); } int main() { int t; scanf("%d",&t); while(t --){ scanf("%d %d",&n,&m); cnt = 0; for(int i=0;i<n;++i){ head[i] = -1; h[i] = i; nxt[i] = -1; ans[i] = -1; parent[i] = i; } for(int i=1;i<=m;++i){ int u,v; scanf("%d %d",&u,&v); addEdge(u,v); addEdge(v,u); } int q; scanf("%d",&q); for(int i=1;i<=q;++i){ int o; scanf("%d",&o); int lastj = -1,nowj = -1; if(head[o]==-1) continue; int temp = h[o]; for(int j=h[o];j!=-1;j=nxt[j]){ bool first = true; int lastV = -1; for(int i=head[j];i!=-1;i=e[i].nxt){ int v = e[i].to,rootV = find(v); if(o==rootV) continue; if(!first){ nxt[rootV] = lastV; } else{ first = false; nxt[rootV] = nxt[j]; nowj = rootV; } if(j==temp) h[o] = h[rootV]; else nxt[lastj] = h[rootV]; h[rootV] = -1; parent[rootV] = o; lastV = rootV; } lastj = nowj; } } for(int i=0;i<n;++i){ ans[i] = find(i); } for(int i=0;i<n;++i){ printf("%d ",ans[i]); } printf("\n"); } return 0; }
全部评论
(1) 回帖