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

2252 줄 세우기 코드도 똑같다. 

종강했다. 할게 많지만 알고리즘은 재밌어서 계속하게되는 것 같다. 

 

[적용한 알고리즘]

위상정렬

 

[아이디어]

[생각의 흐름 / 절차] 

 

[교훈]

위상정렬의 기본 코드라고 한다.

언제나 kks 블로그에서 배운다. 없었으면 큰일 났을 것 같다. 

 

<코드>

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_V = 1002;

int main(){
    int N, M, indegree[MAX_V] = { 0 };
    vector<int> adj[MAX_V];
    scanf("%d %d", &N, &M);

    for (int i = 0; i < M; i++){
        int K; scanf("%d", &K);
        if (K == 0) continue;
        int from, to;
        scanf("%d", &from);

        for (int j = 1; j < K; j++){
            scanf("%d", &to);
            adj[from].push_back(to);
            indegree[to]++;
            from = to;
        }
    }

    int result[MAX_V] = { 0 };
    queue<int> Q;

    for (int i = 1; i <= N; i++){
        if (indegree[i] == 0) Q.push(i);
    }

    for (int i = 1; i <= N; i++){
        if (Q.empty()){
            puts("0");
            return 0;
        }

        int cur = Q.front();
        result[i] = cur;
        Q.pop();

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

    for (int i = 1; i <= N; i++){
        printf("%d\n", result[i]);
    }

    return 0;
}