[baekjoon 2623] 음악프로그램 (위상정렬) (C++)

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

2623번: 음악프로그램

입력값을 인접 그래프로 바꾼 뒤, 위상 정렬을 하면 되는 문제이다.

위상 순서가 여러 줄에 나눠서 주어지지만, 1 2 3을 1-2, 2-3으로 나눠서 생각해서 정리하면 된다.

(가수들끼리의 순서만 유지해서 정리하면 되므로)

또한, 정렬할 수 없을 때 0을 출력해야 하는 조건만 잘 구현해주면 쉽게 풀릴 것이다.

 

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int N, M, T, num, one, in[1001];
vector<int> v[1001], result;
queue<int> q;

void topologySort() {
	for (int i = 1; i <= N; i++) {
		if (in[i] == 0)
			q.push(i);
	}

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		result.push_back(x);

		for (int i = 0; i < v[x].size(); i++) {
			int nx = v[x][i];
			in[nx]--;
			if (in[nx] == 0)
				q.push(nx);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> T;
		cin >> one;
		for (int j = 1; j < T; j++) {
			cin >> num;
			v[one].push_back(num);
			in[num]++;
			one = num;
		}
	}
	topologySort();

	if (result.size() == N) {
		for (auto c : result)
			cout << c << "\n";
	}
	else
		cout<<0;
}