[백준] [C++] 11266번 단절점 (dfs)

1. 문제

단절점이란 한 노드와 인접한간선들을 모두 지웠을 때

 

해당 컴포넌트가 두개 이상으로 나뉘어지는 정점이다.

 

 

11266번: 단절점 (acmicpc.net)

11266번: 단절점

 

2. 무향 그래프 단절점 찾기 : dfs

dfs 스패닝 트리를 생성하고 나면 모든 간선을 4가지로 분류할 수 있다.

 

그 중 단절점 찾기에서 중요한 간선은 역방향 간선으로,

 

자손 노드에서 선조 노드로 연결된 간선이다.

 

한 노드의 자손노드들이 모두 이런 역방향 간선을 통해

 

그 노드의 선조노드로 올라갈 수 있다면

 

절단점이 아니게 되는것이다.

 

 

역방향 간선을 찾는 방법은 간단하다.

 

각 노드를 방문할때, 방문 번호를 오름차순으로 붙이면된다.

 

그리고 간선을 조사할때, 연결된 노드가 더 낮은 번호를 가지고 있으면 역방향 간선이 되는것이다.

 

 

이를 위해 dfs는 역방향 간선을 통해 갈 수 있는 노드들 중 최소인 방문번호를 반환해야한다.

이를 통해 연결된 각각 자손노드들을 검사하여

하나라도 이 노드의 방문번호보다 더 클 경우

이는 이 노드가 절단점이 된다는 것을 알 수 있게된다.

 

dfs 스패닝 트리에서 루트인 경우를 주의해야한다. 만약 자손노드가 하나만 있으면, 이 루트를 삭제해도 두개의 컴포넌트로 분리되지않는다. 반면 자손노드가 두개 이상이면, 이 루트를 삭제하면 무조건 두개의 컴포넌트로 분리된다.

 

#include <bits/stdc++.h>
 
using namespace std;
int V, E;
vector<vector<int> > adjList;
set<int> answer;
 
int dfs(int here, vector<int>& visited, int& visitedNum, bool isRoot) {
    visited[here] = ++visitedNum;
    int ret = visited[here], child = 0;
 
    for(int i = 0; i < adjList[here].size(); i++) {
        int there = adjList[here][i];
        if(visited[there] == -1) {
            child++;
            int subtree =  dfs(there, visited, visitedNum, false);
            if(!isRoot && subtree >= visited[here]) {
                answer.insert(here);
            }
            ret = min(ret, subtree);
        }
        else {
            ret = min(ret, visited[there]);
        }
    }
    if(isRoot && child > 1) {
        answer.insert(here);
    }
    return ret;
}
 
void dfsAll() {
    vector<int> visited(V+1, -1);
    int visitedNum = 0;
    for(int i = 0; i < V; i++) {
        if(visited[i+1] != -1) continue;
        dfs(i+1, visited, visitedNum, true);
    }
    cout<<answer.size()<<"\n";
    for(auto item : answer) {
        cout<<item<<" ";
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin>>V>>E;
    adjList = vector<vector<int> > (V + 1);
    for(int i = 0; i < E; i++) {
        int a, b;
        cin>>a>>b;
        adjList[a].push_back(b);
        adjList[b].push_back(a);
    }
    dfsAll();
}