(20040) 사이클 게임

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

단계별로 풀어보기

34단계(유니온 파인드 1) 4번째

 

 

 

여행 가자 문제에서 두 정점의 연결 여부를 유니온 파인드로 알 수 있다고 했다.

입력으로 들어오는 두 정점을 계속 병합하다가 두 정점이 이미 같은 집합에 속해 있다면 사이클이 발생한 것이다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n >> m;
  
  vector<int> uf(n);
  
  for(int i=1;i<n;i++)  uf[i]= i;
  
  auto find= [&](auto self, int x) -> int {
    if(uf[x]==x)  return x;
    else  return uf[x]= self(self, uf[x]);
  };
  
  auto merge= [&](int x, int y){
    x= find(find, x);
    y= find(find, y);
    
    uf[y]= x;
  };
  
  for(int i=1;i<=m;i++){
    int a, b;
    
    cin >> a >> b;
    
    if(find(find, a)==find(find, b)){
      cout << i;
      
      return 0;
    }
    
    merge(a,b);
  }
  
  cout << 0;
  
  return 0;
}