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

위상정렬(Topological sort)의 아주 기초적인 문제입니다. 매우 기초적인 문제로, 메모리와 시간을 크게 신경 쓰지 않고 구현을 해도 되었으므로, 자료구조를 복습하는 차원에서 구현을 하였습니다.

 

#import<bits/stdc++.h>

using namespace std;
#define endl '\n'
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i, j) for(int i=0;i<j;i++)
#define pb push_back

typedef long long ll;

void solve() {
    int n,m,indegree[1000];
    cin>>n>>m;
    vector<int> v[1000];
    queue<int> q;
    vector<int> result;

    rep(i,m){
        int x,y,z;
        cin>>x;
        if(x == 0)continue;
        cin>>z;
        rep(j,x-1){
            cin>>y;
            v[z-1].pb(y-1);
            indegree[y-1]++;
            z = y;
        }
    }rep(i,n){
        if(indegree[i]==0)q.push(i);
    }
    rep(i,n){
        if(q.empty()){
            cout<<0;
            return;
        }
        int cur = q.front();
        q.pop();
        result.pb(cur+1);
        for(int & x:v[cur])if(--indegree[x] == 0)q.push(x);
    }
    rep(i,n)cout<<result[i]<<endl;
}
int main() {
    fast_io;
    solve();
    return 0;
}

https://www.acmicpc.net/problem/2623