알고리즘 - Connected Component

| 문제

비방향성 그래프 G의 커넥티드 컴포넌트를 의미하는 DFS를 구현하라. DFS 과정을 진행하는 동안, 작은 숫자를 가진 꼭짓점들을 먼저 방문하도록 설계하고, 컴포넌트 숫자는 1로 시작한다.

입력(표준 입력)

첫 번째 줄에는, 꼭짓점의 숫자 N을 입력한다.

다음 줄 부터, 그래프 G의 인접 리스트를 두 정수 x,y로 표현한다. 이것은 x로 시작해서 y로 끝나는 간선이 있음을 의미한다.

출력(표준 출력)

첫 번째 줄에는, 커넥티드 컴포넌트의 숫자를 출력한다.

다음 줄부터 N개의 줄에는, 각각의 꼭짓점의 커넥티드 숫자를 출력한다.

example)

입력	출력
6 1 2 1 4 2 5 3 6	2 1 1 2 1 1 2

| 소스 코드

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

#define TRUE		1
#define FALSE		0

int numV;
int * list;
int * Qlist;
int * rep;

typedef struct _vertex;

typedef struct _vertex
{
	int groupname;
	int value;
	int rank;
	struct _vertex * parent;
} Vertex;

Vertex * vertex;

void MAKE_SET(Vertex * x, int value)
{
	x->value = value;
	x->parent = x;
	x->rank = 0;
}

Vertex * FIND_SET(Vertex * x)
{
	if(x != x->parent)
		x->parent = FIND_SET(x->parent);
	return x->parent;
}

void LINK(Vertex * x, Vertex * y)
{
	if(x->rank > y->rank){
		y->parent = x;			// 랭크가 큰 놈이 부모가 되도록!
	}
	else{
		x->parent = y;
		if(x->rank == y->rank){
			y->rank = y->rank + 1;
		}
	}
}

void UNION(Vertex * x, Vertex * y)
{
	LINK(FIND_SET(x), FIND_SET(y));
}

int SAME_COMPONENT(Vertex * x, Vertex * y)
{
	if(FIND_SET(x) == FIND_SET(y))
		return TRUE;
	else
		return FALSE;
}

int main(void)
{
	int * tmp_list;
	int v1, v2;
	int i=0, j=0, tmp=0;
	int order = 0;
	int compNUM = 0;

	scanf("%d", &numV);
	vertex = (Vertex*)malloc(sizeof(Vertex)*(numV+1));
	list = (int*)malloc(sizeof(int)*(numV+1));
	tmp_list = (int*)malloc(sizeof(int)*(numV+1));
	
	for(i=1; i<=numV; i++)
		MAKE_SET(&vertex[i], i);

	while(scanf("%d %d", &v1, &v2) != EOF){	
		if(FIND_SET(&vertex[v1]) != FIND_SET(&vertex[v2])){
			UNION(&vertex[v1], &vertex[v2]);
		}
	}
	for(i=1; i<=numV; i++){
		list[i] = FIND_SET(&vertex[i])->value;
		tmp_list[i] = FIND_SET(&vertex[i])->value;
	}

	for(i=1; i<=numV; i++)
	{
		tmp = list[i];
		if(tmp != 0)
		{
			compNUM ++;
			for(j=i+1; j<=numV; j++){
				if(tmp == list[j])
					list[j] = 0;
			}
		}
	}
	Qlist = (int*)malloc(sizeof(int)*(compNUM+1));
	order = 1;
	for(i=1; i<=numV; i++){
		if(list[i] != 0){
			Qlist[order++] = list[i];
		}
	}
	for(i=1; i<=numV; i++){
		for(j=1; j<=numV; j++){
			if(tmp_list[i] == Qlist[j]){
				list[i] = j;
			}
		}
	}
	
	printf("%d\n", compNUM);
	for(i=1; i<=numV; i++)
		printf("%d\n", list[i]);

	return 0;
}