[ 백준 / C++ ] 2623 : 음악프로그램

[ 문제 ]

 

2623번: 음악프로그램

 

[ 접근방법 ]

 

위상 정렬을 통해 가수 순서를 파악한다.

 

1. 가수 순서관계를 adj 배열에 저장하고 이를 바탕으로 위상 정렬을 실시한다. 이 때, dfs를 활용한다.

2. 정렬 결과를 ord 벡터에 저장하고 모든 가수 관계를 비교하며 불가능한 경우를 찾는다.

 

[ 소스코드 ]

 

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

void dfs(int node, set<int> adj[], vector<bool> &visited, vector<int> &ord){
    visited[node] = true;
    for(int i : adj[node]){
        if(!visited[i]){
            dfs(i, adj, visited, ord);
        }
    }
    ord.push_back(node);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    set<int> adj[n + 1];
    while(m--){
        int p, q, r;
        cin >> p >> q;
        while(--p){
            cin >> r;
            adj[q].insert(r);
            q = r;
        }
    }

    vector<bool> visited(n + 1, false);
    vector<int> ord;
    for(int i = 1; i <= n; i++){
        if(!visited[i]){
            dfs(i, adj, visited, ord);
        }
    }
    reverse(ord.begin(), ord.end());

    for(int i = 1; i < n; i++){
        for(int j = i + 1; j <= n; j++){
            if(adj[ord[j]].find(ord[i]) != adj[ord[j]].end()){
                cout << "0\n";
                return 0;
            }
        }
    }

    for(int i = 0; i < ord.size(); i++){
        cout << ord[i] << "\n";
    }

    return 0;
}