이중 연결 요소 (BCC, Biconnected Component)

# BCC, 단절점/단절선 O(V+E)
import sys
sys.setrecursionlimit(200005)
input = sys.stdin.readline
​
n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  adj[u].append(v)
  adj[v].append(u)
​
disc = [-1] * n
low = [-1] * n
is_cut = [False] * n
bridges = []
st = []
bcc_list = []
timer = 0
​
def dfs_bcc(u, p):
  global timer
  disc[u] = low[u] = timer
  timer += 1
  children = 0
  for v in adj[u]:
      if v == p: continue
      if disc[v] < 0:
          children += 1
          st.append((u, v))
          dfs_bcc(v, u)
          low[u] = min(low[u], low[v])
          # 단절점 조건
          if (p < 0 and children > 1) or (p >= 0 and low[v] >= disc[u]):
              is_cut[u] = True
              component = []
              while True:
                  a, b = st.pop()
                  component.append((a, b))
                  if a == u and b == v: break
              bcc_list.append(component)
          # bridge 조건
          if low[v] > disc[u]:
              bridges.append((u, v))
      elif disc[v] < disc[u]:
          st.append((u, v))
          low[u] = min(low[u], disc[v])
​
for i in range(n):
  if disc[i] < 0:
      dfs_bcc(i, -1)
# 마지막 남은 간선들도 BCC
if st:
  bcc_list.append(st[:])
​
cut_cnt = sum(is_cut)
print(f"단절점: {cut_cnt}")
print(f"단절선: {len(bridges)}")
print(f"BCC 개수: {len(bcc_list)}")

// BCC, 단절점/단절선 O(V+E)
import java.util.*;
import java.io.*;
​
public class Main {
  static int n, m, timer = 0;
  static List<Integer>[] adj;
  static int[] disc, low;
  static boolean[] isCut;
  static List<int[]> bridges = new ArrayList<>();
  static Stack<int[]> st = new Stack<>();
  static List<List<int[]>> bccList = new ArrayList<>();
​
  static void dfsBcc(int u, int p) {
      disc[u] = low[u] = timer++;
      int children = 0;
      for (int v : adj[u]) {
          if (v == p) continue;
          if (disc[v] < 0) {
              children++;
              st.push(new int[]{u, v});
              dfsBcc(v, u);
              low[u] = Math.min(low[u], low[v]);
              // 단절점 조건
              if ((p < 0 && children > 1) || (p >= 0 && low[v] >= disc[u])) {
                  isCut[u] = true;
                  List<int[]> component = new ArrayList<>();
                  while (!st.isEmpty()) {
                      int[] edge = st.pop();
                      component.add(edge);
                      if (edge[0] == u && edge[1] == v) break;
                  }
                  bccList.add(component);
              }
              // bridge 조건
              if (low[v] > disc[u]) {
                  bridges.add(new int[]{u, v});
              }
          } else if (disc[v] < disc[u]) {
              st.push(new int[]{u, v});
              low[u] = Math.min(low[u], disc[v]);
          }
      }
  }
​
  @SuppressWarnings("unchecked")
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      n = Integer.parseInt(st.nextToken());
      m = Integer.parseInt(st.nextToken());
      adj = new ArrayList[n];
      disc = new int[n];
      low = new int[n];
      isCut = new boolean[n];
      Arrays.fill(disc, -1);
      for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
      for (int i = 0; i < m; i++) {
          st = new StringTokenizer(br.readLine());
          int u = Integer.parseInt(st.nextToken()) - 1;
          int v = Integer.parseInt(st.nextToken()) - 1;
          adj[u].add(v);
          adj[v].add(u);
      }
      for (int i = 0; i < n; i++) {
          if (disc[i] < 0) dfsBcc(i, -1);
      }
      // 마지막 남은 간선들도 BCC
      if (!Main.st.isEmpty()) {
          List<int[]> component = new ArrayList<>();
          while (!Main.st.isEmpty()) component.add(Main.st.pop());
          bccList.add(component);
      }
      int cutCnt = 0;
      for (boolean b : isCut) if (b) cutCnt++;
      System.out.println("단절점: " + cutCnt);
      System.out.println("단절선: " + bridges.size());
      System.out.println("BCC 개수: " + bccList.size());
  }
}