c언어 4803번 트리 (백준)

#include <stdio.h>

int find(int p[], int x) { //부분집합의 대표 노드 찾기
	if(x == p[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;
	return;
}

int main(void) {
	int cnt = 0;
	while(1) {
		cnt++;
		int n, m;
		scanf("%d %d", &n , &m);
		
		if(n>0 || m>0) 
		{
			int p[n+1]; //노드의 부분집합의 대표노드를 담는 곳
			int root[n+1][2]; //[0]은 대표노드의 집합의 요소의 개수, [1]은 대표노드의 집합의 degree의 개수
			int degree[n+1]; //각노드의 degree의 개수를 담는 곳
			for(int i=0; i<=n; i++) {//배열을 초기화
				p[i]=i;
				root[i][0]=0;
				root[i][1]=0;
				degree[i] = 0;
			}
			while(m--) { //정보 입력받기
				int a, b;
				scanf("%d %d", &a, &b);
				merge(p, a, b);
				degree[a]++;
				degree[b]++;
			}
			
			
			for(int i=1; i<=n; i++) { //부분집합의 대표노드를 찾고, 그 부분집합에 속한 요소와, degree 개수 구하기
				int tmp = find(p, i);
				root[tmp][0]++;
				root[tmp][1] += degree[i];
				
			}
			
			int ans = 0; //트리의 개수
			for(int i=1; i<=n; i++) {
				if(root[i][1] == (root[i][0]-1)*2) ans++; //각 트리의 총 degree는 (요소의 개수-1)*2 이다.
			}
			
			printf("Case %d: ", cnt);
			if(ans>1) printf("A forest of %d trees.\n", ans);
			else if(ans) printf("There is one tree.\n");
			else printf("No trees.\n");
		} else break;
	}
}

 

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

 

0. 트리는 사이클이 없습니다. 즉 tree의 degree의 개수는 (트리의 요소개수 -1) * 2 입니다.

//그려보면 이해가 더 잘됩니다.

 

1. union - find을 이용하여, 노드들의 집합들을 합쳐줍니다.

2. 트리를 찾기 위해, 모든 노드들의 부분집합의 대표노드를 찾고, 그 대표노드의 집합에 속한 요소의 개수와, degree의 개수를 구합니다.

3. 만약 부분집합의 degree가 트리의 degree의 조건을 만족한다면, tree라는 의미이며, 그렇지 않으면 그 부분집합은 cycle이 존재한다는 의미입니다.

 

 

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

4803번: 트리