프로그래밍

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

[난이도] Gold4
[유형] 분리집합

[풀이]
Disjoint set을 이용해서 해결할 수 있다.
두 점을 이을때마다 merge 연산을 수행하고, 만약 두 점이 이미 같은 집합이라면
이 두 점을 연결하는 순간 싸이클이 되므로 이 때가 정답이다.

#include <cstdio>
using namespace std;
int N,M,uf[500000];
int find(int a){
    if(uf[a]==a) return a;
    return uf[a] = find(uf[a]);
}
bool merge(int a,int b){
    a=find(a);
    b=find(b);
    if(a==b) return 0;
    uf[a]=b;
    return 1;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++) uf[i]=i;
    for(int i=1;i<=M;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(!merge(u,v)){
            printf("%d",i);
            return 0;
        }
    }
    puts("0");
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/20040.cpp