Union-Find

Union-Find 코드

문제 : 처리해야 하는 총 15개의 값 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 가 있다고 가정하자. 입력 초기에는 15개의 값을 각각 개별 노드, 즉 집합 15개로 구성한다. 구성된 15개의 집합에 대하여 아래 (1), (2), (3)의 순서대로 실행하는 프로그램을 구현하시오.

(1) : Union(1, 2), Union(1, 3), Union(1, 4), Union(3, 5), Union(5, 6), Union(7, 8), Union(9, 10), Union(10, 11), Union(12, 14)의 연산을 순서대로 실행
(2) : (1)번의 연산이 모두 끝난 후, 현재 모든 노드의 root를 출력
(3) : 이후 임의의 두 노드를 입력받아 이들이 같은 집합에 포함되어 있는지 아닌지를 나타내는 확인 결과 출력

---

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

#define MAX_VERTICES 100
#pragma warning(disable:4996)

//부모노드 초기화
int parent[MAX_VERTICES];

// 집합 초기화
void set_init(int n)
{
	for (int i = 0; i < n; i++)
		parent[i] = -1;
}

//curr가 속하는 집합 반환
int Find(int curr)
{
    //루트 반환의 경우
	if (parent[curr] == -1)
		return curr;

	while (parent[curr] != -1)
		curr = parent[curr];

	return curr;
}

// 두개의 원소가 속한 집합을 합친다.
void Union(int a, int b)
{
    //a와 b의 루트를 찾는다.
	int root1 = Find(a);
	int root2 = Find(b);
	
	//합침.
	if (root1 != root2)
		parent[root1] = root2;
}

int main(void)
{
	int a;
	int b;
	char* y = "Y";
	char* n = "N";
	char* answer[1];

	set_init(16);

	//union
	Union(1, 2);
	Union(1, 3);
	Union(1, 4);
	Union(3, 5);
	Union(5, 6);
	Union(7, 8);
	Union(9, 10);
	Union(10, 11);
	Union(12, 14);

	printf("[현재 각 노드의 root를 출력]\n\n");
	for (int i = 1; i < 16; i++) {
		printf("노드 %d의 root는 %d\n", i, Find(i));
	}
	printf("\n[두 노드가 같은 집합에 속하였는지 서로 다른 집합에 속하였는지 여부를 출력]\n");
	
	while (1)
	{
		printf("\n두 개 노드 입력(형식 : 노드1 노드2)) : ");
		scanf_s("%d %d", &a, &b);

		if (Find(a) == Find(b))
			printf("\n노드 %d과 노드 %d는 같은 집합에 속한 노드들입니다..\n", a, b);
		else
			printf("\n노드 %d과 노드 %d는 서로 다른 집합의 노드들입니다\n", a, b);
		
		printf("\n더 입력하려면 Y, 그만하려면 N을 입력하세요 : ");
		scanf("%s", answer);

		if (strcmp(answer, n) == 0)
			exit(1);
	}
}