줄 세우기 - 2252번 백준

문제 

문제 난이도 : 골드 3

문제 분류 : 위상 정렬(Topology Sort)

 

문제 리뷰

Keyword : 진입 차수, Queue

1. 진입 차수 배열 작성
2. (Loop) 진입 차수가 0인 것들을 선택하면서(이 과정에서 위상 정렬의 순서는 단일 되지 않게 됨) 출력한다.
3. (Loop) pop된 부분이랑 연결된 노드의 진입 차수를 감소시킨다. 

위상 정렬 어려울 줄 알았는데 간단하고 명료하다..

문제 소스 코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <memory.h>

using namespace std;

vector<int> Edges[32001];
void Init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    std::cout.tie(NULL);
}


int main()
{
    Init();
    int N, M;
    cin >> N >> M;
    vector<int> Degree(N, 0);
    for (int i = 0; i < M; i++) {
        int A, B;
        cin >> A >> B;
        //A-1의 간선 B-1와 연결
        Edges[A - 1].push_back(B - 1);
        //(B-1)의 진입 차수 증분
        Degree[B - 1]++;
    }
    queue<int> q;
    for (int i = 0; i < N; i++) {
        if (Degree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int top = q.front();
        q.pop();
        cout << top + 1 << " ";
        for (int u : Edges[top]) {
            Degree[u]--;
            if (Degree[u] == 0) {
                q.push(u);
            }
        }

    }

}