위상정렬

topological_sort.cpp

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<vector<int>> singer_vector;
stack <int> result;
bool visited[1001] = { false };
bool finish[1001] = { false };
bool cycle = false;

void DFS(int now_pos) {
	visited[now_pos] = true;
	for (int next_pos : singer_vector[now_pos])
	{
		if (visited[next_pos] == false) {
			DFS(next_pos);
		}
		else if(finish[next_pos] == false){
			cycle = true;
		}
	}
	finish[now_pos] = true;
	result.push(now_pos);
}

int main()
{
	int test_case;
	int singer, sub_PD;
	int how_many_input;
	int prev_singer, curr_singer;

	cin >> test_case;
	while (test_case--) {
		cin >> singer;
		cin >> sub_PD;
		singer_vector.resize(singer + 1);
		for (int i = 0; i < sub_PD; i++) {
			cin >> how_many_input;
			for (int j = 0; j < how_many_input ; j++) {
				if (j == 0) cin >> prev_singer;
				else {
					cin >> curr_singer;
					singer_vector[prev_singer].push_back(curr_singer);
					prev_singer = curr_singer;
				}
			}
		}

		for (int i = 1; i <= singer; i++) {
			if (visited[i] == false) {
				DFS(i);
			}
		}

		if (cycle) cout << 0 << "\n";
		else {
			while (result.size()) {
				cout << result.top() << ' ';
				result.pop();
			}
			cout << "\n";
		}

		cycle = false;
		for (int i = 1; i <= singer; i++) {
			singer_vector[i].clear();
			visited[i] = false;
			finish[i] = false;
		}
	}
}