AtCoder Regular Contest 065 連結

問題

atcoder.jp

問題概要

グラフとグラフで頂点 がどちらも連結しているとき、その数を求めよ。

考察 and 解説

UnionFind木を使う。

UF木で頂点との根が等しい場合、連結であることがわかる。

この問題で求めたいのは、グラフとグラフのどちらでも連結成分が同じものの総数。

これを求めるには、グラフとグラフ用のUF木を作って、根が等しいものの総数を数える。

提出コード

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <map>
using namespace std;

typedef long long ll;

#define INF 10e17 // 4倍しても(4回足しても)long longを溢れない
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())
#define debug(x) std::cerr << (x) << std::endl;
#define roll(x) for (auto itr : x) { debug(itr); }

template <class T> inline void chmax(T &ans, T t) { if (t > ans) ans = t;}
template <class T> inline void chmin(T &ans, T t) { if (t < ans) ans = t;}

/* 必ず要素数をコンストラクタに入れること */
class Union_Find {
public:
  vector<long long> par;
  vector<long long> rnk;

  Union_Find (long long n) {
    par.resize(n), rnk.resize(n);
    for (int i = 0; i < n; ++i) {
      par[i] = i;
      rnk[i] = 0;
    }
  }

  // 木の根を求める
  int find(int x) {
    if (par[x] == x)
      return x;
    else
      return par[x] = find(par[x]);
  }

  // xとyの属する集合を併合
  void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;

    if (rnk[x] < rnk[y]) {
      par[x] = y;
    } else {
      par[y] = x;
      if (rnk[x] == rnk[y]) rnk[x]++;
    }
  }

  // xとyが同じ集合に属するか否か
  bool same(int x, int y) {
    return find(x) == find(y);
  }
};

int main() {
  int n,k,l;
  cin >> n >> k >> l;
  Union_Find uf_road(n+1), uf_train(n+1);

  int r,s;
  rep(i,k) {
    cin >> r >> s;
    uf_road.merge(r, s);
  }

  rep(i,l) {
    cin >> r >> s;
    uf_train.merge(r, s);
  }
  vector<pair<int,int> > com;
  map<pair<int,int>, int> mp;

  for (int i = 1; i <= n; ++i) {
    int a, b;
    a = uf_road.find(i);
    b = uf_train.find(i);
    com.push_back(make_pair(a,b));
    mp[make_pair(a,b)] += 1;
  }

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

  cout << endl;
}