AtCoder Beginner Contest 049 D - 連結 / Connectivity

• 問題

D - 連結 / Connectivity

• 解法

鉄道が枝であるグラフと道路が枝であるグラフそれぞれでUnion-Findを行う。
頂点が鉄道と道路両方で連結であることは、がの同じ連結成分に含まれているかつの同じ連結成分に含まれている、ということと同値である。同じ連結成分に含まれているかどうかはUnion-Find木の根が同じであるかどうかを見ればよい。
頂点と鉄道と道路両方で連結であるような頂点の個数はmapを使うと上手く数えられる。

• 感想

mapあまり使ったことがないので使いこなせるようになりたい。

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

struct union_find{
  vector<int> par,r;

  union_find(int n){
  	par.resize(n);
  	r.resize(n);
  	for(int i = 0; i < n; i++) par[i] = i,r[i] = 0;
  }

  int find(int x){
    if(par[x] == x) return x;
    else return find(par[x]);
  }

  void unite(int x,int y){
    x = find(x);
    y = find(y);
    if(r[x] < r[y]){
      par[x] = y;
    }else{
      par[y] = x;
      if(r[x] == r[y]) r[x]++;
    }
  }

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

int main()
{
	int n,k,l;
	cin >> n >> k >> l;

	union_find road(n),train(n);
	for(int i = 0; i < k; i++){
		int a,b;
		cin >> a >> b;
		a--,b--;
		if(!road.same(a,b)) road.unite(a,b);
	}
	for(int i = 0; i < l; i++){
		int a,b;
		cin >> a >> b;
		a--,b--;
		if(!train.same(a,b)) train.unite(a,b);
	}

	vector<pair<int,int> > com(n);
	map<pair<int,int> ,int> s;
	for(int i = 0; i < n; i++){
		com[i].first = road.find(i);
		com[i].second =  train.find(i);
		s[com[i]]++;
	}

	for(int i = 0; i < n; i++){
		cout << s[com[i]] << " "
	}printf("\n");

	return 0;
}