BOJ 2252 : 줄 세우기

알고리즘 문제 전체 링크

 

https://www.acmicpc.net/problem/2252

 

 

A가 학생 B 앞에 서야 한다는 조건이 있으므로 위상 정렬을 이용하여 풀면 된다.

즉, A → B에 대해 B의 indegree가 1 증가하고, indegree가 0인 학생부터 BFS를 시작하면 된다.

 

설명은 BOJ 1005 : ACM Craft와 동일하다.

#include <stdio.h>

int N, M, A, B;
int indegree[32100];

int queue[100100];
int rp, wp;

typedef struct st
{
	int value;
	struct st *next;
}NODE;

NODE HEAD[32100];
NODE POOL[100100];
int pcnt;

void Make(int p, int c)
{
	NODE *nd = &POOL[pcnt++]; /* POOL에서 메모리를 가져온다 */
	nd->value = c; /* node에 값을 설정. */

	nd->next = HEAD[p].next;
	HEAD[p].next = nd;
}

void BFS()
{
	while (wp > rp)
	{
		int out = queue[rp++];
		printf("%d ", out);

		for (NODE* p = &HEAD[out]; p != NULL; p = p->next)
		{
			int tmp = p->value;

			indegree[tmp]--;

			if (indegree[tmp] == 0) queue[wp++] = p->value;
		}
	}
}

int main(void)
{
	scanf("%d %d", &N, &M);

	for (int i = 1; i <= M;i++)
	{
		scanf("%d %d", &A, &B);

		Make(A, B);
		indegree[B]++;
	}

	for (int i = 1; i <= N;i++)
		if (indegree[i] == 0) queue[wp++] = i;

	BFS();

	putchar('\n');

	return 0;
}