并查集
Clam and Fish
https://ac.nowcoder.com/acm/contest/5668/A
题意:有一个图,有n个点,m条边,点的下标从0到n,对于点i,其开始时属于i—— groud,总共操作q次,每次操作时给出一个n,将所有与n——group直接相连的group加入到n-groud中,在所有操作结束后,求每个点所在的group。在所有操作结束后,求每个点所在的小组。 做题历程:初见不知题中意,再见已是补题人。 做题方法,此题要运用到并查集还有链表,首先是并查集是什么?我搜了一下举例说明。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back const int M = 2e6+7; int pare[M]; int gt(int x) //递归 返回根节点。 { if(x!=pare[x]) pare[x]=gt(pare[x]); return pare[x]; } list<int>G[M]; int main() { int t; cin>>t; while(t--) { int n,m; cin>>n>>m; for(int i=0;i<n;i++) { G[i].clear(); pare[i]=i; } for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; G[x].pb(y); G[y].pb(x); } int q; cin>>q; while(q--) { int x; cin>>x; if(gt(x)!=x) continue; list<int>s; for(int y=0;y<n;y++) { int gy=gt(y); if(gy==x) continue; else pare[gy]=x; s.splice(s.end(),G[gy]);//合并组 } swap(s,G[x]); } for(int i=0;i<n;i++) cout<<gt(i)<<" "<<endl; } return 0; }