강한 연결 요소 (SCC)

// Tarjan, 한 번 DFS + lowlink
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<int> disc, low, scc_id, stk;
vector<bool> on_stk;
int timer = 0, scc_cnt = 0;
void tarjan(int u) {
  disc[u] = low[u] = ++timer;
  stk.push_back(u);
  on_stk[u] = true;
  for (int v : adj[u]) {
      if (!disc[v]) {
          tarjan(v);
          low[u] = min(low[u], low[v]);
      } else if (on_stk[v]) {
          low[u] = min(low[u], disc[v]);
      }
  }
  if (low[u] == disc[u]) {
      while (true) {
          int w = stk.back(); stk.pop_back();
          on_stk[w] = false;
          scc_id[w] = scc_cnt;
          if (w == u) break;
      }
      scc_cnt++;
  }
}
int main() {
  int v, e; cin >> v >> e;
  adj.resize(v + 1);
  disc.assign(v + 1, 0);
  low.assign(v + 1, 0);
  scc_id.assign(v + 1, -1);
  on_stk.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 (!disc[i]) tarjan(i);
  cout << "SCC count: " << scc_cnt << "\n";
  for (int i = 1; i <= v; i++)
      cout << "node " << i << " -> SCC " << scc_id[i] << "\n";
}

# Kosaraju 두 번 DFS
import sys
sys.setrecursionlimit(200005)
input = sys.stdin.readline
​
v, e = map(int, input().split())
adj = [[] for _ in range(v + 1)]
radj = [[] for _ in range(v + 1)]
for _ in range(e):
  a, b = map(int, input().split())
  adj[a].append(b)
  radj[b].append(a)
​
vis = [False] * (v + 1)
stk = []
​
def dfs1(u):
  vis[u] = True
  for w in adj[u]:
      if not vis[w]:
          dfs1(w)
  stk.append(u)
​
for i in range(1, v + 1):
  if not vis[i]:
      dfs1(i)
​
vis = [False] * (v + 1)
scc_id = [-1] * (v + 1)
scc_cnt = 0
​
def dfs2(u, sid):
  vis[u] = True
  scc_id[u] = sid
  for w in radj[u]:
      if not vis[w]:
          dfs2(w, sid)
​
for u in reversed(stk):
  if not vis[u]:
      dfs2(u, scc_cnt)
      scc_cnt += 1
​
print(f"SCC count: {scc_cnt}")
for i in range(1, v + 1):
  print(f"node {i} -> SCC {scc_id[i]}")

// Kosaraju 두 번 DFS
import java.util.*;
import java.io.*;
public class Main {
  static List<List<Integer>> adj, radj;
  static boolean[] vis;
  static int[] sccId;
  static Stack<Integer> stk = new Stack<>();
  static int sccCnt = 0;
  static void dfs1(int u) {
      vis[u] = true;
      for (int v : adj.get(u))
          if (!vis[v]) dfs1(v);
      stk.push(u);
  }
  static void dfs2(int u, int id) {
      vis[u] = true;
      sccId[u] = id;
      for (int v : radj.get(u))
          if (!vis[v]) dfs2(v, id);
  }
  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());
      adj = new ArrayList<>();
      radj = new ArrayList<>();
      for (int i = 0; i <= v; i++) {
          adj.add(new ArrayList<>());
          radj.add(new ArrayList<>());
      }
      vis = new boolean[v + 1];
      sccId = 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);
          radj.get(b).add(a);
      }
      for (int i = 1; i <= v; i++)
          if (!vis[i]) dfs1(i);
      Arrays.fill(vis, false);
      while (!stk.isEmpty()) {
          int u = stk.pop();
          if (!vis[u]) {
              dfs2(u, sccCnt++);
          }
      }
      System.out.println("SCC count: " + sccCnt);
      for (int i = 1; i <= v; i++)
          System.out.println("node " + i + " -> SCC " + sccId[i]);
  }
}