[백준] 2252번 : 줄 세우기 C++ (위상정렬)

접근:

처음에는 어떻게 접근 해야 할지 직접 그려보면서, 관계를 파악해보았다.

대충 봐도 그래프 이론으로 풀어야 하는데, 그 중 순서 정렬이 필요하기 때문에

위상 정렬로 풀어야 한다는 걸 알 수 있다.

 

전략:

대소 관계를 표현하기 위해 입력을 digraph(유향그래프) 형태로 입력을 받는다.(형식은 자유 - 행렬, 인접리스트)

진입 차수가 0인 노드부터 큐에 넣고, 큐에서 하나씩 제거하면서 출력한다.

제거한 노드가 가리키는 다른 노드의 진입 차수를 한개 줄이고, 만약 0이라면 큐에 삽입한다. 

 

코드:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n,m;
vector<vector<int>> comp;
vector<int> income;

int main(){
    cin >> n >> m;
    comp.resize(n+1);
    income.resize(n+1);
    
    for(int i=0;i<m;i++){
        int tall, small;
        cin >> tall >> small;
        comp[tall].push_back(small);
        income[small]++;
    }
    queue<int> inc0;

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

    while(!inc0.empty()){
        auto cur = inc0.front(); inc0.pop();
        cout << cur << ' ';

        for(auto chi: comp[cur]){
            if(--income[chi] == 0){
                inc0.push(chi);
            }
        }
    }
    cout << '\n';
    return 0;
}