ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

KUPC 2014 C 占い

概要


問題文はこちら
http://kupc2014.contest.atcoder.jp/tasks/kupc2014_c

解法


「同じ数字である」という関係を「同じ根を持つ集合」と捉える。

その集合を扱うのにUnionFindTreeを用いる。

違う集合に属している場合はそれらをマージする。

最後にマージしたタイミングが答えとなる。

2人の配列の中身が全て同じ集合に属する → 何回やっても同じ数になる みたいな認識(?)

(本番で解けなかった、こういう問題は思いつけないんだよなぁ...)

ソースコード

#include <bits/stdc++.h>

#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back

using namespace std;

class UnionFindTree {
private:
  int nodeSize;
  vector<int> parent;
  vector<int> rank;
  vector<int> treeSize;

public:
  UnionFindTree(int ns) {
    nodeSize = ns;
    parent = vector<int>(nodeSize); // 親の要素の番号
    rank = vector<int>(nodeSize, 0); // 木の深さ
    treeSize = vector<int>(nodeSize, 1); // 木の要素数

    for(int i = 0; i < nodeSize; i++) {
      parent[i] = i;
    }
  }

  ~UnionFindTree() {}
  
  // 木の根(親の要素)を求める
  int find(int x) {
    if(parent[x] == x) {
      return x;
    }
    else {
      return parent[x] = find(parent[x]);
    }
  }

  // xとyの属する集合を併合
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    
    if(x == y) {
      return;
    }
    
    if(rank[x] < rank[y]) {
      parent[x] = y;
      treeSize[y] += treeSize[x];
    }
    else {
      parent[y] = x;
      treeSize[x] += treeSize[y];
      if(rank[x] == rank[y]) {
        rank[x]++;
      }
    }
  }

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

  // 集合の要素数を得る
  int getSize(int x) {
    return treeSize[find(x)];
  }
};

int N, M, Q;

int main() {
  UnionFindTree uft(200 + 200);

  cin >> N >> M >> Q;
  
  rep(i, Q) {
    int c, d;
    cin >> c >> d;
    uft.unite(c - 1, N + d - 1);
  }

  int ans = 0;
  rep(i, N * M) {
    int k = i % N;
    int u = i % M + N;
    if(!uft.same(k, u)) ans = i + 1;
    uft.unite(k, u);
  }
  
  cout << ans << endl;
}