백준 2252 줄 세우기 - 위상정렬

위상 정렬: 비 순환 방향 그래프에서 그래프의 방향성을 거스르지 않고 정점들을 나열하는 것

그래프에서 반드시 자신보다 선행되어야 할 일을 다 끝내야만 작업에 들어갈 수 있는 조건이 주어질 때 사용한다

 

수행 과정

1. 자기 자신을 가리키는 간선이 없는 정점을 찾아서 큐에 넣음(in-degree가 0인 정점)

2. 큐에서 정점 하나를 출력하고 그 정점에서 출발하는 간선 전부 삭제(간선-=1), 정점도 삭제(pop)

3. 간선을 삭제하다가 간선이 없는 정점이 생기면 큐에 넣음

4. 아직 그래프에 정점이 남아있으면 1번으로 돌아가고, 아니면 종료

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int cnt[32001]; //자신에게 들어오는 간선 개수

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, m;
	cin >> n >> m;

	vector<int> g[32001];
	queue<int> q;

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		cnt[b]++;
	}
	for (int i = 1; i <= n; i++) { //in-degree가 0인 정점 찾기
		if (cnt[i] == 0) q.push(i);
	}

	while(q.size()){
		int now = q.front();
		q.pop();
		cout << now << " ";

		//in-degree가 0인 정점과 연결된 모든 정점 cnt감소(간선 제거)
		for (int j = 0; j < g[now].size(); j++) {
			int next = g[now][j];
			cnt[next]--;
			if (cnt[next] == 0) q.push(next);
		}
		//for (int next : g[now]) {
		//	cnt[next]--;
		//	if (cnt[next] == 0) q.push(next);
		//}
	}
}