백준 2252. 줄 세우기 (위상정렬)

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

2252번: 줄 세우기

1. 특징

1) 위상정렬: 방향 그래프에서 간선이 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬 (사이클이 없는 방향 그래프에서만 잘 정의됨)

 

2. 구현 방식

1) 각 정점으로 들어오는 간선의 개수를 deg배열에 저장함.

int deg[]; //각 정점의 indegree 수

2) deg[i]가 0이 되는 정점은 queue에 삽입

3) queue가 empty가 될 때까지, queue의 front값을 pop하고, 그 정점의 인접 정점의 deg를 -1 해줌.

인접정점의 deg가 0이면, queue에 삽입.

 

3. 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, m;
int u, v;
vector<int> adj[32004];
int deg[32004]; //각 정점의 indegree
int main()
{           
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    for(int i = 0; i < m; i++)
    {
        cin >> u >> v;
        adj[u].push_back(v);
        deg[v]++;
    }

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

    while(!q.empty())
    {
        int cur = q.front(); q.pop();
        cout << cur << ' ';

        for(int nxt:adj[cur])
        {
            deg[nxt]--;
            if(deg[nxt] == 0) q.push(nxt);
        }
    }
}