2623 c++ - 음악프로그램

위상정렬을 사용해서 풀었습니다.
처음에는 조금 헤맸습니다. 뒤에 나오는 값들을 들고있게 만들어야 하나 해서, reverse로 뒤집어 보기도 했는데 그냥 바로 뒤에 있는 값만 들고 있으면 된다는 사실을 깨닫고 풀었습니다.

[그래프/정렬/유향] 위상정렬 / Topological Sorting

 

 

#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

#define FASTIO ios::sync_with_stdio(0), cin.tie(0)

using namespace std;
int n, m;
int main() {
  FASTIO;
  cin >> n >> m;
  vector<int> inDegree(n + 1, 0);
  vector<vector<int>> prioritySinger(n + 1, vector<int>());
  vector<int> result;

  for (int i = 0; i < m; i++) {
    int count;
    cin >> count;

    int singer, nextSinger;
    if (count == 0) continue;
    if (count == 1) {
      cin >> singer;
      continue;
    }

    cin >> singer;
    for (int j = 0; j < count - 1; j++) {
      cin >> nextSinger;
      prioritySinger[singer].push_back(nextSinger);
      inDegree[nextSinger]++;
      singer = nextSinger;
    }
  }

  queue<int> q;

  for (int i = 1; i <= n; i++) {
    if (inDegree[i] == 0) {
      q.push(i);
    }
  }

  while (!q.empty()) {
    int current = q.front();
    q.pop();
    result.push_back(current);

    for (int next : prioritySinger[current]) {
      inDegree[next]--;
      if (inDegree[next] == 0) {
        q.push(next);
      }
    }
  }

  if (result.size() != n) {
    cout << "0";
  } else {
    for (auto d : result) cout << d << "\n";
  }

  return 0;
}