静かで孤独な日記

のんびりたまに

ABC049 D 連結

using namespace std;
//const ll MOD=(ll)1e9+7;
//const ll inf=(ll)1e14;
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];
            //sizes[b]=0;
        }else{
            par[a]=b;
            if(rank[a]==rank[b])rank[b]++;
            sizes[b]+=sizes[a];
            //sizes[a]=0;
        }
    }
    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;
  //FILE *stream2;
  stream1=freopen("in","r",stdin);
  //stream2=freopen("out","w",stdout);
  if(stream1==NULL)return 0;
  //if(stream2==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);
  //fclose(stream2);
#endif
  return 0;
}
  • uf使う感じするよね。
  • でも答えの求め方がわかんなかった。
  • それぞれのufで同じグループだったらオッケーなのを思いつきたかったなぁ。