31. 단절점

단절점이란?

그래프에서 단절점이란 그래프를 두 개 이상의 연결 요소로 분할하는데 필요한 정점이다.

즉, 단절점을 제거하면 그래프가 더 이상 연결되지 않거나, 두 개 이상의 연결 요소로 분할된다.

---

단절점 찾기

단절점을 찾기 위해서는 그래프를 탐색하면서 해당 정점을 제거했을 때 그래프가 분리되는지를 확인해야 한다.

DFS를 이용하여 단절점을 찾을 수 있다.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 100

int adj[MAX_SIZE][MAX_SIZE]; // 인접 행렬
bool visited[MAX_SIZE]; // 방문 여부 배열
int dfn[MAX_SIZE]; // 정점 발견 순서
int low[MAX_SIZE]; // 정점의 low 값
// n: 정점 개수, m: 간선 개수, time: 발견 시간
int n, m, time, root, child_cnt; 

void dfs(int cur, int parent) {
    visited[cur] = true;
    dfn[cur] = low[cur] = ++time;

    for (int i = 0; i < n; i++) {
        if (adj[cur][i]) {
            if (!visited[i]) { // i를 처음 방문한 경우
                if (cur == root) child_cnt++; // 루트일 경우 자식 수 증가

                dfs(i, cur);

                if (low[i] >= dfn[cur]) { // cur이 단절점인 경우
                    printf("%d ", cur);
                }
                low[cur] = low[cur] < low[i] ? low[cur] : low[i];
            }
            else if (i != parent) { // 역방향 간선
                low[cur] = low[cur] < dfn[i] ? low[cur] : dfn[i];
            }
        }
    }
}

void find_articulation_points() {
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            root = i;
            child_cnt = 0;
            dfs(i, -1);

            if (child_cnt > 1) { // 루트의 자식이 2개 이상인 경우
                printf("%d ", root);
            }
        }
    }
}

int main() {
    // 정점 수와 간선 수 입력
    scanf("%d %d", &n, &m);

    // 연결되어 있는 간선 입력
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u][v] = adj[v][u] = 1;
    }

    find_articulation_points();

    return 0;
}

DFS를 이용하여 각 정점을 방문하며, 방문 순서와 low 값 계산을 하고, 단절점을 찾는다.

루트가 단절점인지는 자식 수를 이용하여 판단한다.