using namespace std;
const int dy[]={1,0,-1};
const int dx[]={1,0,-1};
int n,m,h,w;
string s;
int k,l;
class union_find{
public:
explicit union_find(int _n):n(_n){
par.resize(static_cast<unsigned long>(_n));
rank.resize(static_cast<unsigned long>(_n));
sizes.resize(static_cast<unsigned long>(_n));
for(int i=0;i<_n;i++){
par[i]=i;
rank[i]=0;
sizes[i]=1;
}
}
int find(int a){
if(par[a]==a)return a;
return par[a]=find(par[a]);
}
bool same(int a,int b){
return find(a)==find(b);
}
void unite(int a,int b){
link(find(a),find(b));
}
int size(int a){
return sizes[find(a)];
}
void view(){
for(int i=0;i<n;i++){
cout<<" par"<<"["<<i<<"]="<<par[i]<<((i==n-1)?"\n":",");
}
for(int i=0;i<n;i++){
cout<<"size"<<"["<<i<<"]="<<sizes[i]<<((i==n-1)?"\n":",");
}
cout<<endl;
}
private:
void link(int a,int b){
if(same(a,b))return;
if(rank[a]>rank[b]){
par[b]=a;
sizes[a]+=sizes[b];
}else{
par[a]=b;
if(rank[a]==rank[b])rank[b]++;
sizes[b]+=sizes[a];
}
}
int n;
vector<int> par;
vector<int> rank;
vector<int> sizes;
};
int ans[100001];
map<pair<int,int> ,int> mp;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.precision(10);
cout<<fixed;
#ifdef LOCAL_DEFINE
FILE *stream1;
stream1=freopen("in","r",stdin);
if(stream1==NULL)return 0;
#endif
cin>>n>>k>>l;
union_find uf1(n);
for(int i=0;i<k;i++){
int a,b;cin>>a>>b;
a--;b--;
uf1.unite(a,b);
}
union_find uf2(n);
for(int i=0;i<l;i++){
int a,b;cin>>a>>b;
a--;b--;
uf2.unite(a,b);
}
for(int i=0;i<n;i++){
mp[make_pair(uf1.find(i),uf2.find(i))]++;
}
for(int i=0;i<n;i++){
if(i==n-1){
cout<<mp[make_pair(uf1.find(i),uf2.find(i))]<<endl;
}else{
cout<<mp[make_pair(uf1.find(i),uf2.find(i))]<<" ";
}
}
#ifdef LOCAL_DEFINE
cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
fclose(stream1);
#endif
return 0;
}
- uf使う感じするよね。
- でも答えの求め方がわかんなかった。
- それぞれのufで同じグループだったらオッケーなのを思いつきたかったなぁ。