c언어 20040번 사이클 게임 (백준)

#include <stdio.h>

int find(int p[], int x) { //노드가 속한 부분집합의 대표노드를 찾기
	if(p[x] == x) return x;
	return p[x] = find(p, p[x]);
}

void merge(int p[], int x, int y) { //두개의 노드가 속한 부분집합을 결합
	x = find(p, x);
	y = find(p, y);
	if(x!=y) p[x] = y;
}

int main(void) {
	int n, m, cnt = 0;
	scanf("%d %d", &n, &m);
	
	int p[n];
	for(int i=0; i<n; i++) p[i] = i;
	
	while(m--) { 
		cnt++;
		int a, b;
		scanf("%d %d", &a, &b);
		if(find(p, a) == find(p, b)) { //두개의 노드가 같은 집합에 있는지 확인 한다
			printf("%d", cnt); //이미 같은 집합에 있다는 의미는 트리로 연결되어있다는 의미이며
			return 0; //여기서 한번더 연결을 하게 되면 이는 cycle 이 된다.
		}
		merge(p, a, b); //같은 집합이 아니라면 서로를 연결한다.
	}
	printf("0");
}

풀이 : union(합집합) +find(찾기)

0. 사이클은 두 노드가 트리로 연결되어있을 때 (이미 같은 집합에 속해 있을 때) 이 두 노드를 한번 더 연결하면, cycle이 된다.

 

같은 트리에 있는 노드들을 한 번 더 연결하면 사이클이 생기는 것을 볼 수 있다.

 

1. 노드들이 속한 부분집합의 대표노드를 담는 배열을 만든다

2. 두 개의 노드가 같은 집합에 있는 지를 보고

-> 이미 같은 집합이면, 차례를 출력하며

-> 아니라면 두 노드의 부분집합을 합친다.

3. 사이클이 만들어지지 않았다면 0을 출력한다.

 

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

20040번: 사이클 게임