Submission #1061224

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <fstream>
#include <string>
#include <sstream>
#include <math.h>
#include <set>
#include <map>
using namespace std;
#define rep(i,n) for(int i = 0; i < n ; i++)
#define pb push_back
static const int INF = 1000000;
static const int MAX = 200000;

typedef pair<int, int> P;
typedef pair<P, int> PP;

vector<int> G[MAX];
vector<int> G_rail[MAX];

//1はじまりあ
bool grouped[MAX];
bool grouped_rail[MAX];

int groupingNum[MAX];


class DisJointSet {
public:
  vector<int> rank,p;

  DisJointSet(){}
  DisJointSet(int size){
    rank.resize(size,0);
    p.resize(size,0);
    for(int i = 0; i < size; i++) makeSet(i);
  }

  void makeSet(int x){
    p[x] = x;
    rank[x] = 0;
  }

  bool same(int x, int y){
    return findSet(x) == findSet(y);
  }

  void unite(int x, int y){
    link(findSet(x), findSet(y));
  }

  void link(int x, int y){
    if( rank[x] > rank[y] ){
      p[y] = x;
    }else {
        p[x] = y;
        if( rank[x] == rank[y]){
          rank[y] ++;
        }
    }
  }

  int findSet(int x){
    if ( x != p[x] ){
      p[x] = findSet(p[x]);
    }
    return p[x];
  }
};

int main(void){
  int N,K,L; cin >> N >> K >> L;
  DisJointSet road(N+1);
  DisJointSet rail(N+1);
  int a,b;
  rep(i,K){
    cin >> a >> b;
    road.unite(a,b);
  }
  rep(i,L){
    cin >> a >> b;
    rail.unite(a,b);
  }

  map<P,int> mp;
  int c,d;
  rep(i,N){
    c = road.findSet(i+1);
    d = rail.findSet(i+1);
    mp[P(c,d)] += 1;
  }
  rep(i,N){
    c = road.findSet(i+1);
    d = rail.findSet(i+1);
    cout << mp[P(c,d)] << " ";
  }
  cout << endl;

  return 0;
}

Submission Info

Judge Result