단절점

무향 연결 그래프에서 한 노드를 삭제했을 때 두 개의 그래프로 나누어 진다면 해당 노드는 단절점

단절점을 찾아보자

DFS를 돌 때 첫 루프에서 방문한 점은 다 연결되어 있다.

1. 시작 노드인 경우
   자식 수가 2보다 큰 경우 단절점

2. 시작 노드가 아닌 경우
   이 노드의 방문 순서(order)가 연결된 정점의 최소 방문 순서(low)보다 낮은 경우

for(int i=1; i<=N; i++){
    if(order[i] == 0) {
    	dfs(i, true);
    }
}

dfs 돌면서 방문했다면 방문하진 않지만 low 값은 가져온다.

static int dfs(int idx, boolean isRoot) {
    order[idx] = number++;
    int low = order[idx];
    int child = 0;
    for(int next : adjList[idx]) {
    	//방문한 정점이 아닌 경우
        if(order[next] > 0) {
        	low = Math.min(low, order[next]);
            continue;
        }
    
    	child++;
        int min = dfs(next, false);
        
        // 시작노드가 아닌 경우
        // 자식 노드의 low가 현재 노드의 low보다 낮은 경우 단절점이 아니다.
        // 다른 경로를 통해 자식으로 갈 수 있으므로
        if(!isRoot && order[idx] <= min) {
        	isCut[idx] = true;
        }
        
        low = Math.min(low, min);
    }
    
    if(isRoot) {
    	if(child >= 2) isCut[idx] = true;
    }
    
    return low;
}