hyeoneee's blog

단절점이란?

어떤 연결되어 있는 그래프에서 

해당 정점을 없애면, 다른 정점들이 여러 그룹으로 나뉘어 지면 해당 정점이 단절점이다.

그래서 코드는 dfs로 구현하다.

dfs 에서

두가지로 나눈다.

1. 노드가 루트일 경우

-> 밑에 자식이 2 이상이면 단절점이다.

2. 노드가 루트가 아닐경우

dfs로 inOrder를 각 정점에 저장하고

현재 노드의 자식들이 올라갈 수 있는 곳중 가장 높은곳을 리턴받아 그값을 sub라고 하면

그값이 현재 노드의 방문순서보다 더 높으면(크면) 해당 점은 단절점이다.

이게 왜그러냐면, 처음엔 이해가 잘안될 수 있다.

노드 각 정정을 방문하는 순서를 저장하는데  예를들어,

[1,2,3] - [4] - [5,6,7,8] 

이렇게 연결된 노드가 있다고 해보자 크게

그러면 4의 자식인 5~8이 4를 삭제했을때,

1~3을 갈 수 있으면 4는 단절점이 아닌 것이다.

그런데 5~8에서 갈수 있는 곳중 (4를 거치지 않고) 가장 inOrder min값이 5라면 

해당 정점 4는 단절점이다.

샘플코드

    // 시작지점 위치적으로 가장 상위에 있다고 가정 했을때
    // now 노드를 기준으로 하위 sub graph를 탐색했을 때 올라갈 수 있는 가장 높은 위치를 반환
    static int dfs(int now, boolean isRoot) {
        discover[now] = ++inOrder; // 방문순서 마킹
        int res = discover[now]; // 초기값 = 현재 inOrder값
        int child = 0;
        for (int next : adj[now]) {
            if (discover[next] == 0) {//1. 미발견된 노드
                child++; // root일 경우, 단절점 판단을 위해
                int sub = dfs(next, false); // 자식들이 올라갈 수 있는 가장 높은 곳
                if (!isRoot && sub >= discover[now]) {// 루트가 아니고, 자식들이 올라갈 수 있는 가장 높은 곳이 나의 방문 위치보다 더 크다면
                    // 나 이전 노드는 방문 불가
                    isCut[now] = true;
                }
                res = Math.min(res, sub); // 가장 높은곳?
            } else {//2. 발견된노드드
                res = Math.min(res, discover[next]);
            }
        }
        if (isRoot && child >= 2) { // 루트일 경우 단절점 판단
            isCut[now] = true;
        }
        return res;
    }