[boj] 백준 2252 줄 세우기 - 위상정렬

[문제]

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

[풀이]

학생들의 키에 대한 관계가 주어지고 선후 관계가 없을 경우 출력 순서는 상관이 없다. 간단한 위상정렬 문제이다.

 

[코드]

 

#include <iostream>
#include <vector>
#include <queue>

using namespace::std;

int main() {
    int n, m; //n명의 학생, m은 키를 비교한 회수
    int in[100001];
    vector<int> node[32001];

    cin >> n >> m;

    int a, b;
    for(int i=0; i<m; i++){
        cin >> a >> b;
        in[b]++; //진입 차수
        node[a].push_back(b); //인접 관계
    }

    queue<int> q;
    for(int i=1; i<=n; i++){
        if(in[i]==0)
            q.push(i);
    }

    while(!q.empty()){
        int v = q.front();
        q.pop();
        cout << v << " ";

        for(int i=0; i<node[v].size(); i++){
            in[node[v][i]]--;
            if(in[node[v][i]]==0)
                q.push(node[v][i]);
        }
    }
}