L2-024 部落（简单的并查集）

传送门
本题是单纯的并查集(加个排序应该不算加吧）,很简单

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int f[10010];
vector<int> wait[10010];
vector<int> all;
int bet[10010];
int find(int x)
{if(f[x] != x) f[x] = find(f[x]);return f[x];
}void Union(int a,int b){int ra = find(a);
int rb = find(b);if(ra > rb){f[rb] = ra;}else f[ra] = rb;}int main()
{int n;int ans = 0;cin>>n;for(int i = 0 ; i < n ; i++){int k;cin>>k;for(int j = 0 ; j < k ; j ++){int x;cin>>x;wait[i].push_back(x);all.push_back(x);}            }sort(all.begin(),all.end());all.erase(unique(all.begin(),all.end()) , all.end());int cnt = all.size();for(int i = 1; i <= cnt ; i++) f[i] = i;for(int i = 0 ; i < n ; i++){for(int j = 0 ; j < wait[i].size() ; j++){if(j >= 1) Union(wait[i][j],wait[i][j-1]);}}for(int i = 1 ; i <= cnt; i++){int x = find(i);//这里还可以用个bool数组来统计bet[x] ++;if(bet[x] == 1) ans++;}cout<<cnt<<" "<<ans<<endl;int k;cin>>k;while(k--){int l,r;cin>>l>>r;if(f[l] != f[r]) cout<<"N"<<endl;else cout<<"Y"<<endl;}return 0;
}