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

코드

#include <iostream>

using namespace std;

int n,m,res,a,b,lst[500002];

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

void merge(int x, int y) {
  x = find(x);
  y = find(y);
  if(x > y) lst[x] = y;
  else lst[y] = x;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> m;
  for(int i = 0; i < n; i++) lst[i] = i;
  for(int i = 0; i < m; i++) {
    cin >> a >> b;
    if(find(a) != find(b)) {
      merge(a,b);
    } else {
      res = i + 1;
      break;
    }
  }
  cout << res << '\n';
  return 0;
}

접근 방법

무방향 그래프에서 사이클의 유무는 dfs와 유니온 파인드로 확인할 수 있다. 이번 문제는 유니온 파인드로 사이클을 판별했다. 서로 다른 집합에 있던 노드가, 같은 부모를 가진 것이 판명되면 사이클을 가지고 있다고 보면 된다. 같은 부모를 가지고 있는데, 두 그래프를 union 하면 사이클이 생길 것이기 때문이다. 이를테면 아래 그림에서 1,2와 1,3이 연결되었다고 가정했을 때, 2와 3은 1을 부모로 가지고 있다. 이때 2,3을 합치면 사이클이 생긴다. 문제에서는 처음 사이클이 생기는 경우를 출력하라 했으므로 merge하지 않고 몇 번째인지 구한 후 반복문을 탈출하고 출력했다.

 

사이클