[BOJ 2252 / C++] 줄 세우기 (위상정렬)

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

 

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 u, v;
        cin >> u >> v;
        
        adj[u].push_back(v);
        deg[v]++;
    }

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

    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);
        }
    }

    for (int p : result) {
        cout << p << ' ';
    }
}

 

 

2. 시간복잡도

위상정렬은 O(v+e)에 동작한다. v = 32000, e = 10^5 이므로 132000 < 10^8 이므로 시간제한 2초 내에 통과 가능하다.

 

 

3. 분석

DAG (Directed Acyclic Graph)를 인접리스트로 입력받은 후 위상정렬을 수행하면 된다. 스페셜저지이므로 테스트케이스와 답이 다를 수 있다.