185. 줄 세우기

백준

1. 위상 정렬

from collections import deque
n, m = map(int, input().split())

indegree = [0] * (n + 1)
graph = [[] for i in range(n + 1)]

for _ in range(m):
  a, b = map(int,input().split())
  graph[a].append(b)
  indegree[b] += 1


def topology_sort():
  result = []
  q = deque()
  for i in range(1, n+1):
    if indegree[i] == 0:
      q.append(i)

  while q:
    now = q.popleft()
    result.append(now)
    for i in graph[now]:
      indegree[i] -= 1
      if indegree[i] == 0:
        q.append(i)

  for i in result:
    print(i, end=' ')

topology_sort()

C++

#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>

using namespace std;
int in[32001];
vector<int> t[32001];
int main(){
  //m: 간선, n: 노드수
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0, a, b; i < m; i++){
    scanf("%d%d", &a,&b), t[a].push_back(b), in[b]++;

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

  while(!q.empty()){

    int v = q.front(); q.pop();
    result.push_back(v);
    for (int node : t[v])
      if((in[node]-= 1) == 0){
        q.push(node);
        
      }
  }

  for (int r: result){
    printf("%d ", r);
  }
}