백준 2252 줄 세우기 | 위상정렬 | C++

 

 

이번 포스팅은 백준 2252번 줄 세우기입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

 

 

기본 알고리즘

위상정렬 Topological Sort

 

 

전체 코드

 

//백준2252 줄세우기                                                            
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
const int MAX = 32002;
int N, M;
vector<int> adj[MAX];
int inDeg[MAX];
queue<int> q;
vector<int> result;
 
void topoSort() {
    for (int i = 1; i <= N; i++) {
        if (inDeg[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int cur = q.front();
        result.push_back(cur);
        q.pop();
        for (int i = 0; i < adj[cur].size(); i++) {
            int next = adj[cur][i];
            inDeg[next]--;
            if (inDeg[next] == 0) {
                q.push(next);
            }
        }
    }
}
 
int main() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        inDeg[b]++;
    }
 
    topoSort();
 
    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << " ";
    }
 
    return 0;
}