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

20040번: 사이클 게임

 

문제

https://www.acmicpc.net/problem/20040

20040번: 사이클 게임

 

 

풀이

집합 내의 두 정점을 이어주면 같은 컴포넌트(집합)에 속하게 되고 같은 컴포넌트끼리 연결을 해줄 때 사이클이 생긴다. 유니온 파인드 알고리즘을 사용해 해결할 수 있다.

 

연결할 두 정점을 입력받고 두 정점이 같은 컴포넌트인지만 확인하면 된다. 만약 이미 같은 컴포넌트라면 해당 연결에서 사이클이 생성되므로 몇 번째 연결인지 출력하고 프로그램을 종료하면 된다. 그렇지 않다면 두 정점을 union 해서 같은 컴포넌트로 만들어 준다. 모든 연결을 수행했음에도 아직 종료되지 않았다면 0을 출력하고 종료한다.

 

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> p;

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

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, M;
  cin >> N >> M;
  p.resize(N);
  iota(p.begin(), p.end(), 0);
  for (int i = 1; i <= M; i++) {
    int x, y;
    cin >> x >> y;
    if (find(x) == find(y)) {
      cout << i;
      return 0;
    }
    merge(x, y);
  }
  cout << 0;
  return 0;
}