THINK-PRO BLOG

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

#define WHITE			0
#define GRAY			1
#define BLACK			2

#define TREE_EDGE		1
#define BACK_EDGE		2
#define FORWARD_EDGE	3
#define CROSS_EDGE	4

#define TRUE			1
#define FALSE			0

typedef struct _vertex{
	int color;
	int f;
	int d;
} Vertex;

typedef struct _VertexInfo{
	int out_degree;
	int * list;
} VertexInfo;

Vertex * vertex;
VertexInfo * vertexInfo;
int numV, time;
int * topoList;
int topo_num=0;
int isDAG = TRUE;

void addEdge(int fromV, int toV){
	int i=0;
	int cur=0;

	for(i=0; i < numV; i++)
	{
		if(vertexInfo[fromV].list[i] == 0)
			break;
		cur ++;
	}
	vertexInfo[fromV].list[cur] = toV;
}

void DFS_Visit(int fromV){
	int i=0, toV;

	/* DISCOVERED */
	time++;
	vertex[fromV].color = GRAY;
	vertex[fromV].d = time;

	for(i=0; i < vertexInfo[fromV].out_degree; i++){
		toV = vertexInfo[fromV].list[i];
		switch(vertex[toV].color)
		{
		case WHITE:
			DFS_Visit(toV);
			break;

		case GRAY:
			isDAG = FALSE;
			break;

		case BLACK:
			break;
		default:
			break;
		}
	}

	/* FINISHED */
	vertex[fromV].color = BLACK;
	topoList[numV-(topo_num++)] = fromV;
	time ++;
	vertex[fromV].f = time;
}

void Sort(int * list, int num)
{
	int i=0, j=0, tmp;

	for(i=0; i < num; i++)
	{
		for(j=i+1; j < num; j++)
		{
			if(list[i] > list[j])
			{
				tmp = list[i];
				list[i] = list[j];
				list[j] = tmp;
			}
		}
	}
}


void DFS(void)
{
	int i;
	for(i=1; i <=numV; i++)
	{
		vertex[i].d = 0;
		vertex[i].f = 0;
		vertex[i].color = WHITE;
		Sort(vertexInfo[i].list, vertexInfo[i].out_degree);
	}

	time = 0;
	for(i=1; i <=numV; i++)
	{
		if(vertex[i].color == WHITE)
		{
			DFS_Visit(i);
		}
	}
}


int main(void)
{
	int i=0, j=0;
	int fromV, toV;

	scanf("%d", &numV);

	/* INITIALIZATION START! */
	vertexInfo = (VertexInfo*)malloc(sizeof(VertexInfo)*(numV+1));
	for(i=1; i <=numV; i++){
		vertexInfo[i].list = (int*)malloc(sizeof(int)*numV);
		vertexInfo[i].out_degree = 0;
	}
	for(i=1; i <=numV; i++){
		for(j=0; j < numV; j++){
			vertexInfo[i].list[j] = 0;
		}
	}
	vertex = (Vertex*)malloc(sizeof(Vertex)*(numV+1));
	topoList = (int*)malloc(sizeof(int)*(numV+1));
	/* INITIALIZATION END! */
	

// INPUT
	while(scanf("%d %d", &fromV, &toV)!=EOF){
		addEdge(fromV, toV);
		vertexInfo[fromV].out_degree ++;
	}
	DFS();

// OUTPUT
	printf("%d\n", isDAG);
	if(isDAG)
	{
		for(i=1; i <=numV; i++)
			printf("%d ", topoList[i]);
	}

	return 0;
}

#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;
}

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

#define minus_inf -32767

int PARENT(int index){ return index/2; }
int LCHILD(int index){ return index*2; }
int RCHILD(int index){ return index*2+1; }

void array_swap(int arr[], int a, int b)
{
	int temp;
	temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}

void Heapify(int arr[], int current, int length)
{
	int left, right, largest;
	left=LCHILD(current);
	right=RCHILD(current);

	if((right<=length) && (arr[right]>arr[current]))
		largest = right;
	else
		largest = current;

	if((left<=length) && (arr[left]>arr[largest]))
		largest = left;

	if(largest != current)
	{
		array_swap(arr, current, largest);
		Heapify(arr, largest, length);
	}
}

void PRINT(int arr[], int length)
{
	int i=0;
	for(i=1; i<=length; i++)
		printf("%d ", arr[i]);
}

int EXTRACT_MAX(int arr[], int length)
{
	if(length < 1)		// "heap underflow"
		return minus_inf;
	int max = arr[1];
	arr[1] = arr[length];
	length --;
	Heapify(arr, 1, length);
	return max;
}

void INCREASE_KEY(int arr[], int index, int key)
{
	int tmp=0;
	if(key < arr[index])		// not increasing, then fail.
		return;

	arr[index] = key;
	while(index>1 && arr[PARENT(index)]<arr[index])
	{
		/* EXCHANGE CURRENT WITH PARENT */
		tmp = arr[index];
		arr[index] = arr[index/2];
		arr[index/2] = tmp;

		index = PARENT(index);
	}
}

void INSERT(int arr[], int length, int key)
{
	arr[length] = minus_inf;
	INCREASE_KEY(arr, length, key);
}

int main(void)
{
	int arr[100000];
	int ext[100000];
	int length=0, extlength=0;

	int op, tmp, i;
	int index, num;

	int quit=0;

	//INSERT(arr, length, 1); length++;
	//INSERT(arr, length, 2); length++;

	while(quit==0)
	{
		scanf("%d", &op);
		switch(op)
		{
		case 0:// print
			quit=1;		// terminate this program.
			break;

		case 1:// insert
			scanf("%d", &num);
			length++;
			arr[length] = num;
			INCREASE_KEY(arr, length, num);
			break;

		case 2:// extract
			extlength++;
			ext[extlength] = arr[1];

			tmp = arr[1];
			arr[1] = arr[length];
			arr[length] = tmp;

			length--;
			Heapify(arr, 1, length);
			break;

		case 3:// replace
			scanf("%d %d", &index, &num);
			arr[index] = num;
			if(index != 1 && arr[index] > arr[PARENT(index)])
				INCREASE_KEY(arr, index, num);
			else
				Heapify(arr, index, length);
			break;
	
		default:
			break;
		}
	}

	for(i=1; i<=extlength; i++)
		printf("%d ", ext[i]);

	printf("\n");
	for(i=1; i<=length; i++)
		printf("%d ", arr[i]);

	return 0;
}