코드 복사/붙여넣기 하는 당신이 아름답습니다.

2623 : 음악프로그램

풀이

위상정렬을 하면 된다!

코드

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

const int n_ = 1000 + 3;

int n, m, idg[n_];
vector<int> ans;
vector<int> edg[n_];

void dfs(int now) {
	idg[now] = -1;
	ans.push_back(now);
	for (auto nxt : edg[now])
		if (!(--idg[nxt])) dfs(nxt);
}

int main() {
	int i, j, a, b, c;
	cin >> n >> m;
	while (m--) {
		cin >> a >> b;
		while (--a) {
			cin >> c;
			edg[b].push_back(c);
			idg[c]++;
			b = c;
		}
	}
	for (i = 1; i <= n; i++)
		if (!idg[i]) dfs(i);
	
	if (ans.size() < n) puts("0");
	else for (auto p : ans) printf("%d\n", p);

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-03-13 11:19

Read more posts by this author