글 읽기 - [자료구조]

tjdgns9246 7년 전 0

서로소 집합에서 간단한 개념을 이용한 합집합 연산 simpleUnion()

서로소 집합에서 간단한 개념을 이용한 찾기 연산 simpleFind()

서로소 집합에서 가중법칙을 이용한 합집합 연산 weightedUnion()

서로소 집합에서 붕괴법칙을 이용한 찾기 연산 collapsingFind()

<input>

<output>

Enter the size of disjoint-set : 8

Test for simple union & find :

1 a

2 b

3 c

4 d

5 e

6 f

7 g

-1 h

-----------------

Test for weighted union & collapsing find :

0 b

-----------------

2 d

0 c

-----------------

4 f

0 e

-----------------

6 h

4 g

0 e

-----------------

After collapsing :

0 b

-----------------

0 d

-----------------

0 f

-----------------

0 h

-----------------

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

typedef struct
{
	int parent, count;
	char name;
} node;

node* list1, *list2;
node simpleFind(node* list, int i);
node collapsingFind(node* list, int i);
void simpleUnion(node* list, int i, int j);
void weightedUnion(node* list, int i, int j);

int main()
{
	int n;
	printf("Enter the size of disjoint-set : ");
	scanf("%d", &n);
	printf("%d\n\n", n);
	
	list1 = (node *)malloc(sizeof(node) * n);
	list2 = (node *)malloc(sizeof(node) * n);
	for(int i = 0; i < n; i++)
	{
		list1[i].parent = list2[i].parent = -1;
		list1[i].count = list2[i].count = 1;
		list1[i].name = list2[i].name = 'a' + i;
	}
	
	// test for simeple union & find
	printf("Test for simple union & find :\n");
	for(int i = 0; i < n - 1; i++)
		simpleUnion(list1, i, i + 1);
	simpleFind(list1, 0);
	printf("-----------------\n\n");
	
	// test for weighted union & collapsing find
	for(int i = 1; i < 8; i += 2)
		weightedUnion(list2, i - 1, i);
	weightedUnion(list2, 0, 2);
	weightedUnion(list2, 4, 6);
	weightedUnion(list2, 0, 4);
	for(int i = 0; i < 2; i++)
	{
		for(int j = 1; j < 8; j += 2)
		{
			collapsingFind(list2, j);
			printf("-----------------\n");
		}
	}
}

node simpleFind(node* list, int i)
{
	for(; list[i].parent > -1; i = list[i].parent)
		printf("%d %c\n", list[i].parent, list[i].name);
	printf("%d %c\n", list[i].parent, list[i].name);
	return list[i];
}

node collapsingFind(node* list, int i)
{
	int root, trail, lead;
	
	for(root = i; list[root].parent > -1; root = list[root].parent)
		printf("%d %c\n", list[root].parent, list[root].name);
		
	for(trail = i; trail != root; trail = lead)
	{
		lead = list[trail].parent;
		list[trail].parent = root;
	}
	return list[root];
}

void simpleUnion(node* list, int i, int j)
{
	list[i].parent = j;
}

void weightedUnion(node* list, int i, int j)
{
	int temp = list[i].count + list[j].count;
	if(list[i].count < list[j].count)
	{
		list[i].parent = j;
		list[j].count = temp;
	}
	else
	{
		list[j].parent = i;
		list[i].count = temp;
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[자료구조] - Disjoint Set

tjdgns9246 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말