dh_0e

[PS] 음악 프로그램 / C++ (백준 2623번) 본문

알고리즘/Baekjoon

[PS] 음악 프로그램 / C++ (백준 2623번)

dh_0e 2024. 11. 21. 15:45

 

위상 정렬 기초를 다지기 좋은 문제

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<deque>
using namespace std;
deque<int> dap;
int vi[1001];
int d[1001][1001];
int n, m;

int find()
{
    for(int i=1; i<=n; i++){
        if(d[i][0]==0&&vi[i]==0){
            vi[i]=1;
            return i;
        }
    }
    return -1;
}

int main()
{
    scanf("%d %d",&n, &m);
    for(int i=1; i<=m; i++){
        int k, be;
        scanf("%d %d",&k, &be);
        for(int j=1; j<k; j++){
            int c;
            scanf("%d",&c);
            if(d[c][be]==0)d[c][0]++;
            d[c][be]=1;
            be=c;
        }
    }
    for(int i=1; i<=n; i++){
        int idol=find();
        if(idol==-1){
            printf("0\n");
            return 0;
        }
        dap.push_back(idol);
        for(int j=1; j<=n; j++){
            if(d[j][idol]==0)continue;
            d[j][0]--;
            d[j][idol]=0;
        }
    }
    while(!dap.empty()){
        printf("%d\n",dap.front());
        dap.pop_front();
    }
    return 0;
}