[알고리즘 정리] 위상 정렬

위상 정렬

시간 복잡도 : O(|V|+|E|)

indegree : 한 정점에 들어오는 간선 수

ex ) a -> c, b -> c 라면 c의 indegree는 2, a,b의 indegree는 0이 된다.

기본 코드

// 해당 노드에 향하는 간선(indegree)이 0인경우 q에 추가한다.
for (int i = 1; i <= n; i++)
	if (indegree[i] == 0)
		q.push(i);

while (!q.empty())
{
	// 큐에서 하나의 노드를 가져온다.
	int cur = q.front();
	q.pop();

	// 현재 cur노드에서 indegree를 감소시키며 이동한다.
	while (!v[cur].empty())
	{
		int next = v[cur].back();
		v[cur].pop_back();
		indegree[next]--;
		// 노드의 indegree가 0이되면 큐에 넣는다.
		if (indegree[next] == 0)
			q.push(next);
	}
	// 노드를 저장한다.
	ans.push_back(cur);
}
	
// 만약 주어진 모든 노드를 이용하여 하나의 위상정렬을 할 수 있는지 물어본다면!
// indegree가 0이 아닌 노드가 존재한다면 불가능하다!
for (int i = 1; i <= n; i++)
{
	if (indegree[i] != 0)
	{
		printf("0");
		return 0;
	}
}

기본 예제

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

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <queue>
#include <utility>
#include <functional>
#define MAX 40005
#define MOD 1000000007
#pragma warning(disable:4996)
using namespace std;

int n, m, a, b, c, indegree[32005];
vector<int> v[32005], ans;
queue<int> q;

int main()
{
	fill_n(&indegree[0], 32005, 0);
	scanf("%d %d", &n, &m);

	for (int i = 0; i < m; i++)
	{
		scanf("%d %d", &a, &b);
		for (int k = 0; k < a - 1; k++)
		{
			scanf("%d", &c);
			v[b].push_back(c);
			// b->c를 향하는 간선을 저장한다.
			indegree[c]++;
			// c 노드에 향하는 간선의 개수를 저장한다.
			b = c;
		}
	}
	// 입력을 받아 온다.

	// 해당 노드에 향하는 간선(indegree)이 0인경우 q에 추가한다.
	for (int i = 1; i <= n; i++)
		if (indegree[i] == 0)
			q.push(i);

	while (!q.empty())
	{
		// 큐에서 하나의 노드를 가져온다.
		int cur = q.front();
		q.pop();

		// 현재 cur노드에서 indegree를 감소시키며 이동한다.
		while (!v[cur].empty())
		{
			int next = v[cur].back();
			v[cur].pop_back();
			indegree[next]--;
			// 노드의 indegree가 0이되면 큐에 넣는다.
			if (indegree[next] == 0)
				q.push(next);
		}
		// 노드를 저장한다.
		ans.push_back(cur);
	}
	
	// 만약 주어진 모든 노드를 이용하여 하나의 위상정렬을 할 수 있는지 물어본다면!
	// indegree가 0이 아닌 노드가 존재한다면 불가능하다!
	for (int i = 1; i <= n; i++)
	{
		if (indegree[i] != 0)
		{
			printf("0");
			return 0;
		}
	}

	for (int i = 0; i < ans.size(); i++)
		printf("%d\n", ans[i]);
	return 0;
}