BOJ2252: 줄 세우기

작성일

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

  • 1월동안 100문제 풀기 (10/100)
  • 드디어.. 10문제. 잘 아는 Topological Sort 문제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

int N, M, A, B;
vector<vector<int>> adj;
vector<int> inbound;

int main() {
  ios::sync_with_stdio(false);
  cin >> N >> M;
  adj.resize(N+1);
  inbound.resize(N+1);

  for(int i = 0; i < M; i++) {
    cin >> A >> B;
    adj[A].push_back(B);
    inbound[B]++;
  }

  queue<int> q;
  for(int i = 1; i <= N; i++)
    if(inbound[i] == 0) q.push(i);

  while(q.size()) {
    int cur = q.front(); q.pop();
    cout << cur << " ";
    for(int near: adj[cur]) {
      if(--inbound[near] == 0)
        q.push(near);
    }
  }
}