[백준] 줄 세우기

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

2252번: 줄 세우기

우선 문제부터 간단하게 요약하면, 

 

학생들을 줄 세우는데, 두 학생의 키 비교 결과만 주어질 때, 해당 모든 조건을 만족하도록 학생들을 줄세워 출력하는 문제입니다.

 

<Solution>

전형적인 위상정렬의 문제로 위상정렬을 구현하면 됩니다. 실제 구현은 아래와 같습니다.

#include <iostream>
#include <queue>

using namespace std;

int N, M;

queue <int> nodeQ;
int indegree[32000+1];
vector<int> graph[32000+1]; // 인접리스트

vector<int> ans;

int main(){

    cin >> N >> M;
    int s,e;

    for(int i = 0 ; i<M ;i++){
        cin >> s >> e;
        graph[s].push_back(e); // 인접리스트 update
        indegree[e] += 1; // 진입차수 증가
    }

    // topological sort
    for(int i = 1; i<N+1; i++){
        if(indegree[i]) continue;
        nodeQ.push(i);
    }

    while(!nodeQ.empty()){
        int node = nodeQ.front(); nodeQ.pop();
        ans.push_back(node);

        for(int i : graph[node]){
            indegree[i]--;
            if(!indegree[i]) nodeQ.push(i);
        }
    }

    for(int i : ans){
        cout << i << ' ';
    }
    cout << endl;

    return 0;
}