[백준] 2623번 - 음악프로그램

음악프로그램(백준, 2623번)

• 링크 : https://www.acmicpc.net/problem/2623

풀이

#pragma warning(disable:4996)
#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
#include <random>
#include<time.h>
#include<string>
#include<queue>
#include <set>
#include <map>
#include <list>
#include<stack>
#include<deque>
#include<cstring>
#define MAX 26
#define INF 987654321
using namespace std;


int n, k;
vector<int> res;
vector<vector<int>> graph;
vector<int> indegree;



int main(void) {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    cin >> n >> m;

    indegree = vector<int>(n + 1, 0);
    graph = vector<vector<int>>(n + 1);

    for (int subPd = 0; subPd < m; subPd++) {
        int T; cin >> T;
        vector<int> tmp(T);
        for (int idx = 0; idx < T; idx++) {
            cin >> tmp[idx];
        }

        for (int idx = 0; idx < T - 1; idx++) {
            int cur = tmp[idx];
            int next = tmp[idx + 1];
            graph[cur].push_back(next);
            indegree[next]++;
        }
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (!indegree[i]) {
            res.push_back(i);
            q.push(i);
        }
    }
    if (!q.size()) {
        cout << 0 << endl;
        exit(0);
    }

    while (!q.empty()) {
        int cur = q.front(); q.pop();

        for (int nxt = 0; nxt < graph[cur].size(); nxt++) {
            int next = graph[cur][nxt];
            indegree[next]--;
            if (indegree[next] < 0) {
                cout << 0 << endl;
                exit(0);
            }
            if (!indegree[next]) {
                res.push_back(next);
                q.push(next);
            }
        }
    }
    if (res.size() < n) {
        cout << 0 << endl;
        exit(0);
    }

    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << endl;
    }
    return 0;
}

• 바보같이 출력 형식을 안읽고 풀어서, 왜 틀렸지.... 하고 오랫동안 고민함...
• 0이 나오는 case는 크게 두가지가 있다. 잘 하면 합칠 수 있겠으나 내 여가시간에 여백이 모자라서 적지 않음.