Articulation Point (단절점)

단절점(https://www.acmicpc.net/problem/11266) 문제에 대한 코드, 템플릿을 만들어주세요!

코드

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> g[10001];
int discovered[10001], cnt;
bool ans[10001];

int dfs(bool is_root, int node)
{
    int i, ret, child = 0, low;
    discovered[node] = ++cnt;
    ret = discovered[node];

    for ( i = 0; i < g[node].size(); i++ ) {
        int u = g[node][i];
        if ( discovered[u] == 0 ) {
            child++;
            low = dfs(false, u);
            if ( is_root == false && low >= discovered[node] )
                ans[node] = true;
            ret = min(ret, low);
        }else
            ret = min(ret, discovered[u]);
    }

    if ( is_root && child >= 2 ) ans[node] = true;
    return ret;
}

int main()
{
    int v, e, a, b, i, cnt = 0;

    scanf("%d%d", &v, &e);
    while(e--) {
        scanf("%d%d", &a, &b);
        g[a].push_back(b);
        g[b].push_back(a);
    }

    for ( i = 1; i <= v; i++ )
        if ( discovered[i] == 0 )
            dfs(true, i);

    for ( i = 1; i <= v; i++ )
        if ( ans[i] )
            cnt++;

    printf("%d\n", cnt);
    for ( i = 1; i <= v; i++ )
        if ( ans[i] )
            printf("%d ", i);

    return 0;
}

정리

• 단절점을 제거하고 요소 개수가 늘었는지 확인하는 방법은 각 단절점에 대한 dfs 를 수행하므로 시간복잡도는 O(V(V+E)) 이다. 스패닝 트리를 이용하면 O(V+E) 에 해결할 수 있다.
• 알고리즘의 아이디어
  • 단절점 경로 이외의 우회 경로가 존재할 경우, 단절점이 아니다.
  • 스패닝 트리이기 때문에 DFS 를 순회할 때, 방문순서를 기재하게 되면 일반적으로 자식이 부모보다 큰 값을 가져야 한다
  • 만약 우회경로가 있다면 자식이 부모보다 더 작게된다
  • 결론적으로 자식들의 DFS 의 min 이 현재 방문순서보다 작다면(미만) 단절점이 아니라고 할 수 있다
  • 루트의 경우 자식이 1개 이하라면 단절점이 아니므로, 루트에 대해서만 예외적으로 자식이 2개 이상일때 단절점이다.
• 구현 내용
  • DFS 탐색을 시작해서 방문하는 순서로 정점에 번호를 매긴다. (스패닝트리를 만든다)
  • 루트 일 경우
    • 자식이 2개 이상이면 단절점
  • 루트가 아닐 경우
    • 자식의 방문순서의 최소값이, 현재 탐색중인 노드의 방문순서보다 같거나 클 경우 단절점이다.

관련 문제

• 단절점 (https://www.acmicpc.net/problem/11266)

참고 자료

• 종만북 854페이지
• http://bowbowbow.tistory.com/3