[BOJ 2623 / C++] 음악프로그램 (위상정렬)

문제링크: https://www.acmicpc.net/problem/2623

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

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

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

    vector<vector<int>> adj(n+1);
    vector<int> deg(n+1, 0);

    for (int i = 0; i < m; i++) {
        int num;
        cin >> num;
        vector<int> tmp(num);
        for (int j = 0; j < num; j++) {
            cin >> tmp[j];
        }

        for (int j = 0; j < num-1; j++) {
            adj[tmp[j]].push_back(tmp[j+1]);
            deg[tmp[j+1]]++;
        }
    }

    queue<int> Q;
    vector<int> result;

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

    while (!Q.empty()) {
        int cur = Q.front(); Q.pop();
        result.push_back(cur);
        for (int nxt : adj[cur]) {
            deg[nxt]--;
            if (deg[nxt] == 0) Q.push(nxt);
        }
    }

    if (result.size() != n) {
        cout << 0;
    }
    else {
        for (int p : result) {
            cout << p << '\n';
        }
    }
}

 

 

2. 시간복잡도

위상정렬의 시간복잡도는 O(n+e)에 동작한다. 문제에서 n = 1000 이하 정수이고 간선 개수 e = m*100이므로 연산 횟수는 2000 < 10^8이므로 시간제한 1초내에 통과 가능하다.

 

 

3. 분석

전형적인 위상정렬 문제이다. 입력을 받을 때 전체를 입력받아놓고 adjacent_list에 하나씩 정점과 간선 정보를 입력해주면 된다.