[BOJ] 2623 : 음악프로그램 - travelbeeee

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

---

위상정렬

● inDegree가 0인 지점부터 시작해서 위상 정렬을 진행한다. 이때, 탐색하는 순서대로 노드들을 vector<int> ans 에 저장하고, 탐색한 노드들을 check 한다. 탐색이 끝나면 모든 노드들을 check 했다면 가능한 순서쌍이 존재하는 것이므로 ans를 차례대로 출력해주고, 모든 노드들을 check 하지 못했다면 불가능한 경우이므로 0을 출력한다.

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

using namespace std;

int N, M, inDegree[1001];
vector<int> graph[1001] = {};
vector<int> ans;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	// Input 처리
	cin >> N >> M;
	for (int i = 0, k; i < M; i++) {
		int list[1000];
		cin >> k;
		for (int j = 0; j < k; j++)
			cin >> list[j];
		for (int j = 0; j < k - 1; j++){
			graph[list[j]].push_back(list[j + 1]);
			inDegree[list[j + 1]]++;
		}
	}
	// 위상정렬
	stack<int> s;
	bool check[1001] = {};
	for (int i = 1; i <= N; i++)
		if (inDegree[i] == 0)
			s.push(i);
	while (!s.empty()) {
		int cur = s.top(); s.pop();
		ans.push_back(cur);
		check[cur] = true;
		for (int i = 0; i < graph[cur].size(); i++) {
			inDegree[graph[cur][i]]--;
			if (inDegree[graph[cur][i]] == 0)
				s.push(graph[cur][i]);
		}
	}
	// 다 체크되었는지!
	bool flag = false;
	for (int i = 1; i <= N; i++) {
		if (check[i] == 0){
			flag = 1;
			break;
		}
	}
	if (!flag) {
		for (int j = 0; j < ans.size(); j++)
			cout << ans[j] << '\n';
	}
	else
		cout << 0;

	return 0;
}

---