BOJ)2623 음악프로그램

문제: icpc.me/2623

음악프로그램의 출연 순서의 리스트가 주어졌을 때 모든 리스트를 만족시키도록 출연 순서를 출력하는 문제이다.

만약 모든 리스트를 만족할 수 없는 경우 0을 출력하면 된다.

우리는 출연 순서가 A->B->C 라면 A->B / B->C의 방향으로 간선을 연결해 준 뒤 topology를 구해줌으로서 리스트를 구할 수 있다.

이때 모든 리스트를 만족할 수 없는 경우는 사이클이 생기는 경우로서 그래프의 사이클 여부를 체크해줌으로서 확인 가능하다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#define MAX_N 1000
using namespace std;
int n, m, k, x, y, cycle, visited[MAX_N + 1], finish[MAX_N + 1];
vector<vector<int>>vt;
stack<int> st;
void dfs(int here) {
    visited[here] = true;
    for (auto there : vt[here]) {
        if (!visited[there])
            dfs(there);
        else if (!finish[there])
            cycle = 1;
    }
    finish[here] = true;
    st.push(here);
}
int main() {
    scanf("%d%d", &n, &m);
    vt.resize(n + 1);
    for (int i = 0; i < m; i++) {
        scanf("%d", &k);
        for (int j = 0; j < k; j++) {
            if (!j)
                scanf("%d", &x);
            else {
                scanf("%d", &y);
                vt[x].push_back(y);
                x = y;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!visited[i])
            dfs(i);
    }
    if (cycle)
        printf("0\n");
    else {
        while (st.size()) {
            printf("%d\n", st.top());
            st.pop();
        }
    }
    return 0;
}