위상 정렬 (Topological Sorting)

// DFS post-order 역순
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<bool> vis, rec;
vector<int> stk;
bool cycle = false;
void dfs(int u) {
  vis[u] = rec[u] = true;
  for (int v : adj[u]) {
      if (rec[v]) { cycle = true; return; }
      if (!vis[v]) dfs(v);
  }
  rec[u] = false;
  stk.push_back(u);
}
int main() {
  int v, e; cin >> v >> e;
  adj.resize(v + 1);
  vis.assign(v + 1, false);
  rec.assign(v + 1, false);
  for (int i = 0; i < e; i++) {
      int a, b; cin >> a >> b;
      adj[a].push_back(b);
  }
  for (int i = 1; i <= v; i++)
      if (!vis[i]) dfs(i);
  if (cycle) {
      cout << "CYCLE\n";
  } else {
      reverse(stk.begin(), stk.end());
      for (int x : stk) cout << x << " ";
      cout << "\n";
  }
}

# Kahn's BFS
from collections import deque
import sys
input = sys.stdin.readline
​
v, e = map(int, input().split())
adj = [[] for _ in range(v + 1)]
indeg = [0] * (v + 1)
for _ in range(e):
  a, b = map(int, input().split())
  adj[a].append(b)
  indeg[b] += 1
​
Q = deque(i for i in range(1, v + 1) if indeg[i] == 0)
res = []
while Q:
  u = Q.popleft()
  res.append(u)
  for w in adj[u]:
      indeg[w] -= 1
      if indeg[w] == 0:
          Q.append(w)
​
if len(res) < v:
  print("CYCLE")
else:
  print(" ".join(map(str, res)))

// Kahn's in-degree BFS
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int v = Integer.parseInt(st.nextToken());
      int e = Integer.parseInt(st.nextToken());
      List<List<Integer>> adj = new ArrayList<>();
      for (int i = 0; i <= v; i++) adj.add(new ArrayList<>());
      int[] indeg = new int[v + 1];
      for (int i = 0; i < e; i++) {
          st = new StringTokenizer(br.readLine());
          int a = Integer.parseInt(st.nextToken());
          int b = Integer.parseInt(st.nextToken());
          adj.get(a).add(b);
          indeg[b]++;
      }
      Queue<Integer> Q = new LinkedList<>();
      for (int i = 1; i <= v; i++)
          if (indeg[i] == 0) Q.add(i);
      List<Integer> res = new ArrayList<>();
      while (!Q.isEmpty()) {
          int u = Q.poll();
          res.add(u);
          for (int w : adj.get(u)) {
              if (--indeg[w] == 0) Q.add(w);
          }
      }
      if (res.size() < v) {
          System.out.println("CYCLE");
      } else {
          for (int x : res) System.out.print(x + " ");
          System.out.println();
      }
  }
}