백준 02623 - 음악프로그램

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

2623번: 음악프로그램

 

고려 사항

• 위상 정렬 알고리즘!
• 주어진 정보를 활용하여,
  vector[가수 번호] = { 연결된 노드 리스트 ( 연결 당한 노드들 ) },
  array[가수 번호] = 연결 당한 횟수.
• 연결 당한 횟수가 0 인 가수 번호를 큐에 삽입.
• 큐가 비지 않으면 반복해서,
  1. 정답 벡터에 제일 먼저 들어온 가수를 담고 pop 한다.
  2. 그 가수가 연결한 가수 번호들의 cnt 를 -1 해주고,
  3. 그 결과값이 0이면 큐에 삽입
• 큐가 비어서 반복문을 빠져 나왔을 때,
  1. 정답 벡터에 가수 수인 n 만큼 담겼으면 출력.
  2. 아니라면, 라인업 짜기 불가능, 0 출력!

 

#include <iostream>
#include <queue>
using namespace std;

queue<int> q;
int n, m, t, singer;
int cnt[1001];
bool visit[1001];
vector<int> s[1001];
vector<int> v, answer;

int main() {

    cin>>n>>m;
    for(int i=0;i<m;++i){
        cin>>t;
        for(int j=0;j<t;++j){
            cin>>singer;
            v.push_back(singer);
        }

        for(int j=1;j<t;++j){
            s[v[j-1]].push_back(v[j]);
            ++cnt[v[j]];
        }

        v.clear();
    }

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

    while(!q.empty()){
        int next = q.front();
        answer.push_back(next);
        q.pop();

        for(int i : s[next]){
            --cnt[i];
            if(cnt[i] == 0){
                q.push(i);
            }
        }
    }

    if(answer.size() == n){
        for(int i : answer){
            cout<<i<<"\n";
        }

        return 0;
    }

    cout<<"0";
    return 0;
}