백준 - 음악프로그램 (2623) [C++]

이 문제는 dfs, 위상 정렬을 이용해서 풀었다.

 

위상 정렬과 더불어 방향 그래프에서의 사이클 판정을 할 수 있으면 쉽게 풀리는 문제였다.

 

방향 그래프에서는 dfs 변형을 통해 사이클 판정을 할 수 있고, 무방향 그래프에서는 유니온 파인드를 이용해서 사이클 판정을 할 수 있다. 방향 그래프에서 유니온 파인드를 써보면 제대로 답이 나오지 않는다.

 

위상 정렬은 원래 dfs를 이용해서 푸는 방식을 선호했는데, 요구 사항이 복잡해지는 문제를 잘 해결하지 못하는 경우가 많았다. 그러나 incoming 카운트를 세어서 queue에 넣어 위상정렬하는 방식은 문제 요구 사항이 추가되어도 변형이 쉬운 편이고, 구현도 직관적이다. 이 문제에서는 후자의 방식으로 풀 수 있었다.

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

#define MAX 1000

int N, M;
vector<int> edges[MAX + 1];
int incoming[MAX + 1];
int visited[MAX + 1];

bool dfs(int now) {
	if (visited[now] == -1) {
		return true;
	}
	if (visited[now] == 1) {
		return false;
	}
	visited[now] = -1;
	for (int next : edges[now]) {
		if (dfs(next)) {
			return true;
		}
	}
	visited[now] = 1;
	return false;
}

bool isCycle() {
	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			bool result = dfs(i);

			if (result) {
				return true;
			}
		}
	}
	return false;
}

void topoSort() {
	queue<int> q;
	
	for (int i = 1; i <= N; i++) {
		if (!incoming[i]) {
			q.push(i);
		}
	}

	while (!q.empty()) {
		int present = q.front();
		q.pop();

		cout << present << '\n';

		for (int next : edges[present]) {
			incoming[next]--;

			if (!incoming[next]) {
				q.push(next);
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int cnt;
		cin >> cnt;

		vector<int> temp(cnt);
		for (int i = 0; i < cnt; i++) {
			cin >> temp[i];
		}

		for (int i = 1; i < cnt; i++) {
			int prev = temp[i - 1];
			int here = temp[i];

			edges[prev].push_back(here);
			incoming[here]++;
		}
	}

	if (isCycle()) {
		cout << 0 << '\n';
	} else {
		topoSort();
	}

	return 0;
}