| 문제
비방향성 그래프 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;
}
'컴퓨터 프로그래밍' 카테고리의 다른 글
| 배열의 이름은 포인터가 아니다? (0) | 2014.02.16 |
|---|---|
| 알고리즘 - Topological Sort (위상 정렬) (0) | 2014.02.15 |
| 알고리즘 - Priority Queue(우선순위 큐를 구현하라) (0) | 2014.02.15 |
| 알고리즘 - Heap Sort (힙 소트(힙 정렬)를 구현하라) (0) | 2014.02.15 |
| 알고리즘 - DFS(Depth-First Search) 깊이 우선 탐색 소스 코드 (0) | 2014.02.15 |