백준) 2623 음악프로그램

음악프로그램

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

줄 세우기 문제(http://js1jj2sk3.tistory.com/94?category=755224)와 같은 위상정렬문제다.

다만 간선을 만드는 과정과 사이클의 유무를 확인하는 데 유의하자.

#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
 
int n, m, a, b, c;
int in[1001];
 
int main() {
    scanf("%d %d", &n, &m);
    vector<vector<int>> vec(n+1);
 
    for (int i = 0; i < m; ++i) {
        scanf("%d", &a);
        scanf("%d", &b);
        for (int j = 1; j < a; ++j) {
            scanf("%d", &c);
            vec[b].push_back(c);
            in[c]++;
            b = c;
        }
    }
 
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (!in[i])
            q.push(i);
    }
 
    vector<int> ans;
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        ans.push_back(t);
 
        for (auto next : vec[t]) {
            in[next]--;
            if (!in[next])
                q.push(next);
        }
    }
 
    if (ans.size() != n) {
        printf("0");
        return 0;
    }
 
    for (auto a : ans)
        printf("%d\n", a);
    return 0;
}