[BOJ] 2252 : 줄 세우기 - travelbeeee

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

---

[ 알고리즘풀이 ]

 전형적인 위상 정렬 문제입니다.

 입력에 맞춰 graph를 그리고, 노드마다 inDegree 값을 구해 inDegree가 0인 노드부터 시작해 해당 노드와 연결된 노드들의 inDegree 값을 깎아가며 inDegree가 0이 된 노드들을 추가로 탐색해나가면 됩니다.

#include<iostream>
#include<vector>
#include<stack>

using namespace std;
int N, M, inDegree[32001];
vector<int> list[32001];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;
	for (int i = 0, x, y; i < M; i++) {
		cin >> x >> y;
		list[x].push_back(y);
		inDegree[y]++;
	}
	stack<int> s;
	for (int i = 1; i <= N; i++) {
		if (inDegree[i] == 0)
			s.push(i);
	}

	while (!s.empty()) {
		int cur = s.top();
		s.pop();
		cout << cur << ' ';
		for (int i = 0; i < list[cur].size(); i++) {
			inDegree[list[cur][i]]--;
			if (inDegree[list[cur][i]] == 0)
				s.push(list[cur][i]);
		}
	}

	return 0;
}

---