백준 20040번 사이클 게임[C++]

1. 문제 풀이

 문제를 처음 읽었을 때, 그래프 자료구조에 간선이 하나씩 추가될 때마다 dfs를 통해 사이클을 탐지하는 naive 한 풀이 방법이 먼저 떠올랐습니다. 문제의 입력을 그래프 자료구조로 보게 되면 정점이 n개이고 간선이 m개인 그래프를 입력받는데 정점이 최대 500'000개이고 간선은 1'000'000개라 이러한 풀이 방법은 시간 내 정답을 구할 수 없다는 생각이 들었습니다.

 생각의 발상으로 분리 집합(disjoint-set)을 구현하는 union-find 알고리즘을 사용하면 이 문제를 풀이할 수 있습니다. 두 선분을 잇는다를 두 점을 한 집합으로 union한다고 생각하시면 됩니다. 사이클을 탐지하는 방법은 이 union-find가 진행되는 과정을 그림으로 그려보시면 알 수 있는데 서로 같은 집합에 속한 두 점 사이에 선분이 그어지게 되면 사이클이 생기게 됩니다. 이미 이어져있는 선분을 다시 잇지 않는다고 하였으므로 다른 조건사항이 붙지 않아도 됩니다.

 union-find에서 경로압축과 union-by-rank를 모두 사용하여 최적화한 경우 union, find 모두 시간복잡도가 아커만 역함수를 가집니다. 이는 상수 시간과 매우 가까운 성능을 가지므로 O(1)로 보고 계산하게 된다면 O(M)이 되겠습니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n, m;
vi p(500'005, -1);

int find(int x){ return (p[x] < 0 ? x : p[x] = find(p[x])); }

bool merge(int x, int y){
  x = find(x);
  y = find(y);
  if(x == y) return 0;
  if(p[x] == p[y]) p[x]--;
  if(p[x] > p[y]) swap(x, y);
  p[y] = x;
  return 1;
}

int main() {
  fastio(nullptr, false);

  // input
  cin >> n >> m;
  
  // solve
  int ans = 0x3f3f3f3f;
  for(int round = 1; round <= m; round++){
    int u, v;
    cin >> u >> v;
    if(!merge(u, v)){
      ans = round;
      break;
    }
  }

  // output
  cout << (ans == 0x3f3f3f3f ? 0 : ans);
}

 

3. 제출 결과