c언어 1717번 집합의 표현 (백준)

#include <stdio.h>
#include <stdlib.h>

int find(int parent[], int x) { //노드가 속한 부분집합의 대표노드 찾기
	if(parent[x] == x) return x; //자기자신이면 자기자신을 리턴
	return parent[x] = find(parent, parent[x]); //자기자신이 아니면, 부분집합의 대표노드의 대표노드 찾기
}

void merge(int parent[], int x, int y) { //두개의 노드가 속한 집합 합치기
	x = find(parent, x); //x의 대표 노드//사실 노드를 합치면 알아서 그 두개의 집합이 연결된다.
	y = find(parent, y); //y의 대표노드
	if(x==y); //같은 노드이면 이미 같은 집합이다.
	else parent[x] = y; //다르면 어떤 하나 대표노드를 다른 노드의 대표노드에 대입한다.
    return; //parent[y] = x; //도 상관없다
}

int same(int parent[], int x, int y) { //두개의 노드가 같은 집합인지를 찾는 함수
	x = find(parent, x); //노드 x의 대표노드
	y = find(parent, y); //노드 y의 대표노드
	return x == y; //대표노드가 같다면 같은 부분집합에 있다는 의미이다.
}

int main(void) {
	int n, m;
	scanf("%d %d", &n, &m);
	int *parent = (int*) malloc(sizeof(int)*(n+1));
	for(int i=1; i<=n; i++) parent[i] = i;
	
	while(m--) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		
		if(!a) merge(parent, b, c);
		else {
			if(same(parent, b, c)) printf("YES\n");
			else printf("NO\n");
		}
	}
}

풀이 : union(합집합) find(찾기) 을 사용했습니다.

 

 

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

1717번: 집합의 표현