단절점 [BOJ 11266]

단절점 [BOJ 11266] (P5 & Class 6)

https://www.acmicpc.net/problem/11266

11266번: 단절점

 

단절점이란?

 

하나의 컴포넌트로 구성된 무방향 그래프에서 특정 정점을 제거했을 때 두 개 이상의 컴포넌트로 나누어지는 정점

 

하나의 컴포넌트로 구성된 무방향 그래프

빨간색 정점 1, 6, 7이 단절점

위 그래프에서 빨간색 정점이 1, 6, 7이 단절점이다.

1, 6, 7 중 하나를 없애면 그래프가 2개 이상의 덩어리로 분리되기 때문이다.

 

DFS Spanning Tree

 

한 그래프에서 특정 정점에서 시작하여 DFS를 하였을 때 방문하는 정점들을 연결하여 만든 트리 모양의 그래프이다.

 

위 그래프의 DFS Tree의 모습

그래프를 DFS Tree로 변환 후

- 트리에도 존재하는 간선 : tree edge

- 트리의 자손-조상 사이 간선 : back edge

- 그 외 간선 : cross edge

위 그림의 검은색 간선은 모두 tree edge, 파란색 간선은 back edge이다.

 

Idea Motivation

 

1. V가 리프 노드인 경우에는 당연히 남은 점들이 모두 tree edge로 연결되어 있으므로 단절점이 아니다

 

2. V가 루트 노드인 경우 다음 2가지로 생각해 볼 수 있다.

 

① 자식 노드가 2개 이상

여러 개의 서브트리가 연결되기 위해서는 서브트리들을 모두 이어주는 cross edge들이 존재해야한다.

하지만 어떤 두 서브트리 사이 간선이 존재했다면 DFS할 때 서브트리를 종료하기 전 해당 정점을 방문했을 것이다.

즉, 루트 노드의 두 서브트리 사이에는 cross edge가 존재할 수 없다!

= V가 단절점

 

② 자식 노드가 1개

제거해도 나머지 노드가 모두 tree edge로 연결되어 있다!

= V가 단절점이 아니다

 

3. V가 그 외 정점인 경우

 

① DFS Tree에서 V의 자손인 정점들 중 V를 거치지 않고 한번에 V의 부모 노드로 가는 back edge가 존재한다.

= 해당 점을 잘라도 자신의 아래와 위가 연결되어 있다.

= V가 단절점이 아니다

 

② 반대의 경우

= 해당 점을 제거하면 자신의 아래와 위를 연결해줄 간선은 없다.

= V가 단절점

 

구현

 

V가 리프 노드인 1번 경우와 일반적인 노드인 3번 경우를 분리해줄 필요는 없다.

V가 루트 노드인 경우만 예외 처리해주면 된다.

아래는 BOJ 11266번에 맞게 구현된 코드이다.

 

#include <bits/stdc++.h>
#define SIZE 10001
using namespace std;
/*
g : 인접리스트
ord[i] : i번 정점의 DFS 방문 순서
par[i] : i번 정점의 부모 노드
low[i] : i번 정점을 루트로 하는 서브트리에서 간선 하나만 거쳐서 갈 수 있는 정점 중 가장 작은 low 값
ret : 단절점을 저장하는 set
*/

vector<int> g[SIZE];
set<int> ret;
int par[SIZE], ord[SIZE], low[SIZE], t;
void dfs(int v)
{
    ord[v]=low[v]=++t;
    int sub=0;
    for (int i : g[v]) if (i!=par[v]) {
        if (!ord[i]) {
            par[i]=v, sub++;
            dfs(i);
            if (!par[v] && sub>1) ret.insert(v); // v가 루트 노드
            else if (par[v] && low[i]>=ord[v]) ret.insert(v); // v가 루트 노드가 아닌 경우
            low[v]=min(low[v], low[i]);
        }
        else low[v]=min(low[v], ord[i]); // 이미 방문한 정점
    }
}
int main()
{
    int N, M, s, e, i;
    scanf ("%d %d", &N, &M);
    while (M--) {
        scanf ("%d %d", &s, &e);
        g[s].push_back(e);
        g[e].push_back(s);
    }
    for (i=1; i<=N; i++) if (!ord[i]) dfs(i);
    cout << ret.size() << endl;
    for (auto i : ret) printf("%d ", i);
}

 

아래 블로그를 참고하여 공부했다.

https://justicehui.github.io/hard-algorithm/2019/01/06/ArticulationPoint/