[백준] 11266: 단절점

0. 문제 주소

 

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

11266번: 단절점

 

 

1. 풀이

 

단절점이란, 제거했을 때 그래프가 둘 이상의 컴포넌트로 나뉘는 정점을 의미한다.

 

DFS를 이용해 각 정점들을 돌면서, 방문 순서 번호를 order배열에 저장한다.

 

그리고 low라는 것을 정의하는데, curr node의 low는 min(curr의 order, next node의 order, next node의 low)로 정의한다.

 

그림 그리기 귀찮으니까.... 대충 말로 설명해보자면

 

어떤 점이 단절점일 때엔, 그 점으로부터 DFS 탐색을 계속 이어갔던 정점들은

어떠한 방법으로도 단절점의 order보다 더 작은 order를 가지는 정점으로 갈 수 없다. (DFS시 방문 여부 상관와 상관없이)

 

그래서 위와 같이 low를 정의하고, 이번 노드의 order보다 low가 크거나 같다면 위에서 묘사한 상황이 된다고 이해하면 된다.

 

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <iostream>
#include <vector>

#define MAX 10005

using namespace std;

int V, E;
vector<int> graph[MAX];
int cnt;
int order[MAX];
int ans_cnt;
bool ans[MAX];

int DFS(int curr, bool is_Root){
    order[curr] = ++cnt;
    
    int ret = order[curr];
    int child = 0;
    for (auto next: graph[curr]){
        if (!order[next]){
            child++;
            int low = DFS(next, false);
            if (!is_Root && order[curr] <= low){
                ans[curr] = true;
            }
            ret = min(ret, low);
        }
        else{
            ret = min(ret, order[next]);
        }
    }
    
    if (is_Root){
        ans[curr] = (child >= 2);
    }
    
    return ret;
}

int main(){
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	#endif
	
	scanf("%d %d", &V, &E);
	int u, v;
	for (int i=0;i<E;i++){
	    scanf("%d %d", &u, &v);
	    graph[u].push_back(v);
	    graph[v].push_back(u);
    }
    
    for (int i=1;i<=V;i++){
        if (!order[i]){
            DFS(i, true);
        }
    }
    
    for (int i=1;i<=V;i++){
        if (ans[i]) ans_cnt++;
    }
    
    printf("%d\n", ans_cnt);
    for (int i=1;i<=V;i++){
        if (ans[i]){
            printf("%d ", i);
        }
    }
	
	

	return 0;
}