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

음악프로그램
https://www.acmicpc.net/problem/2623

2623번: 음악프로그램

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> arr[1001];
int check[1001]{0};
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, M;
    cin >> N >> M;
    for(register int m = 0, cnt; m < M; ++m){
        cin >> cnt;
        vector<int> tmp;
        for(register int c = 0, n; c < cnt; ++c)
            cin >> n, tmp.push_back(n);
        for(register int i = 0, j; i < tmp.size() - 1; ++i)
            for(j = i + 1; j < tmp.size(); ++j)
                arr[tmp[i]].push_back(tmp[j]), ++check[tmp[j]];
    }
    queue<int> q, ans;
    for(register int n = 1; n <= N; ++n)
        if(!check[n])
            q.push(n);
    while(!q.empty()){
        auto pos = q.front(); q.pop();
        ans.push(pos);
        for(auto& v : arr[pos]){
            if(--check[v] == 0)
                q.push(v);
        }
    }
    if(ans.size() != N)
        cout << 0;
    else
        while(!ans.empty())
            cout << ans.front() << '\n', ans.pop();
	return 0;
}
// *&)*@*

 

반응형

위상정렬을 이용하는 문제입니다.

PD의 번호는 문제의 풀이에 영향을 주지 않고, PD가 정한 가수의 순서가 핵심입니다.