c언어 13244번 Tree (백준)

#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;
}

int main(void) { 
    int t; //몇번
    scanf("%d", &t);
    
    while(t--) {
        int n, m; //노드개수, 간선 정보 몇번 입력?
        scanf("%d %d", &n, &m);
        
        int p[n+1]; //노드가 속한 집합의 대표노드 
        int degree[n+1]; //노드의 degree 개수
        int cnt[n+1][2]; //부분 집합의 대표인가? [0]    대표라면 부분집합의 degree의 개수는? [1]
        
        for(int i=1; i<=n; i++) { //배열 초기화
            p[i] = i;
            degree[i] = 0;
            cnt[i][0] = cnt[i][1] = 0;
        }
        
        while(m--) { //집합 합치기
            int a, b;
            scanf("%d %d", &a, &b);
            degree[a]++; //각각의 ㅣ노드의 degree을 올리다보니, 실제 degree에 비해 두배정도가 된다.
            degree[b]++;
            merge(p, a, b);
        }
        
        for(int i=1; i<=n; i++) { //부분집합의 대표집합 찾기
            int tmp = find(p, i);
            cnt[tmp][0]++; //어떤노드가 부분집합의 대표집합이면 1이상으로
            cnt[tmp][1] += degree[i]; //그 부분집합의 degree의 개수를 누적
        }
        
        int tree = 0; //tree의 개수
        for(int i=1; i<=n; i++) {
            if((cnt[i][0]-1)*2 == cnt[i][1]) tree++; //tree는 부분집합의 간선의 개수가 (노드의 수 -1) * 2 이다.
            //물론 실제론 (노드의 수 -1)이 맞으나, 이 코드는 2배로 degree을 증가시켯기 때문에 나누기를 한다.
            if(cnt[i][0] && cnt[i][1]==0) tree++; //tree는 부분집합의 노드의 개수가 1이며, 간선의 개수가 0 인것도 tree입니다.
        }
        
        if(tree == 1) printf("tree\n"); //트리의 개수가 1개이면 tree
        else printf("graph\n"); //트리의 개수가 여러개이면 또는 없다면, 전체적으론 graph입니다.
    }
}

 

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

 

1. union find을 이용하여 부분집합들을 합칩니다.

2. 집합들을 합칠 때, 노드들과 연결된 degree의 개수를 증가시켜줍니다.

3. 부분집합의 대표노드들을 찾고, 그 부분집합의 노드의 개수와, 노드들의 degree의 개수를 구합니다.

4. 부분집합의 대표노드들을 이용하여, 그 부분집합이 tree인지 아닌지를 구분합니다.

5. 만약 모든 노드가 하나의 tree로만 이루어져 있다면, 이는 전체적으로 tree라는 의미이여

트리가 여러개 있거나 0개있다면 이는 전체적으로 graph라는 의미입니다.

 

 

dfs 등의 방식으로도 풀 수 있다고 합니다!

 

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

13244번: Tree