cut point, cut line

단절점

시간 복잡도 : O(N + M)

vector<vector<int> > graph;
vector<int> discovered;
vector<bool> isCut;

int start_node = 1

// here == 정점 A
int findCutPoint(int here, bool isRoot) {
  discovered[here] = start_node;  // DFS 탐색 순서 지정
  start_node += 1;

  int ret = discovered[here];
  int child = 0;

  for (int next : graph[here]) {
    // 만약 이미 DFS에서 탐색된 정점이라면
    // 현재 정점의 방문순서와 탐색된 정점의 방문 순서중 min값을 찾는다.
    // 이 방법을 이용해야
    // " A번 정점에서 자식 노드들이 정점 A를 거치지 않고
    // 정점 A보다 빠른 방문번호를 가진 정점으로 갈 수 없다면 단절점이다. "
    // 를 찾을 수 있다.
    if (discovered[next]) {
      ret = min(ret, discovered[next]);
      continue;
    }

    child++;
    int prev = findCutPoint(next, false);

    // 정점 A가 루트가 아니라면
    // A번 정점에서 자식 노드들이 정점 A를 거치지 않고 정점 A보다 빠른
    // 방문번호를 가진 정점으로 갈 수 없다면 단절점이다.
    if (!isRoot && prev >= discovered[here]) isCut[here] = true;

    ret = min(ret, prev);
  }

  // 정점 A가 루트 라면, 자식 수가 2개 이상이면 단절점이다.
  if (isRoot) {
    if (child >= 2) {
      isCut[here] = true;
    }
  }

  return ret;
}

사용

for (int i = 1; i <= V; i++) {
  if (!discovered[i]) findCutPoint(i, true);
}

단절선

vector<vector<int>> graph;
vector<int> discovered;
// from, to
vector<pair<int, int>> cutLines;

int findCutLine(int here, int parent) {
  discovered[here] = start_node;
  start_node += 1;

  int ret = discovered[here];

  for (int next : graph[here]) {
    if (next == parent) continue;

    if (discovered[next]) {
      ret = min(ret, discovered[next]);
      continue;
    }

    int prev = findCutLine(next, here);

    if (prev > discovered[here]) {
      int from = min(here, next);
      int to = max(here, next);

      cutLines.push_back({from, to});
    }

    ret = min(ret, prev);
  }

  return ret;
}

사용법

for (int i = 1; i <= V; i++) {
  if (!discovered[i]) findCutLine(i, 0);
}