문제 출처

1. 문제설명

  • 보조 PD들이 만든 순서들이 입력으로 주어질 때, 전체 가수 순서를 정하라
    • 모두가 만족하는 순서 출력
    • 만약 불가능 하다면 0
  • 문제 분류
    • Graph, Topological Sorting


2. 알고리즘 설계

  • 위상정렬(Topological Sorting) 기본 문제이다.
  • 이전 문제와 달리 위상 정렬의 조건이 성립하지 않는지까지 체크한다.
  • 위상 정렬은 한번도 가르켜지지않은 노드들을 순차적으로 큐에 집어넣고, 하나씩 꺼내면서 현재 노드가 가르키는 노드의 가르킴 횟수를 줄인다.
    • 그리고 만약 가르킴 횟수가 0이라면 큐에 넣는다.
  • 여기서 큐가 비어서 루프가 끝났다. 그렇다면 어떤 결과값이 보장되어야 할까?
    • 위상 정렬 결과를 노드번호로 벡터에 저장했다면, 벡터의 원소의 개수와 원래 원소의 개수가 같아야 한다.
    • 그렇다! 루프 종료 후에 N == res.size()를 체크해주면 이번 문제와 이전 문제는 차이가 거의 없다.


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int SZ = 1'002;
int n, m, cnt, a, b, deg[SZ];
vector<int> adj[SZ], res;
queue<int> q;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    while(m--) {
        cin >> cnt;
        cin >> a;
        for(int i=1; i<cnt; i++) {
            cin >> b;
            adj[a].push_back(b);
            deg[b]++;
            a = b;
        }
    }

    for(int i=1; i<=n; i++)
        if(deg[i] == 0) q.push(i);
    
    while(!q.empty()) {
        int cur = q.front();
        q.pop();

        res.push_back(cur);

        for(int nxt : adj[cur]) {
            deg[nxt]--;
            if(deg[nxt] == 0) q.push(nxt);
        }
    }

    if(res.size() != n) cout << 0;
    else 
        for(int a : res) cout << a << '\n';

    return 0;
}