[백준] [C++] 11400번 단절선 (dfs)

1. 문제

11400번: 단절선 (acmicpc.net)

 

2. 풀이

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

단절점 문제와 유사하다.

 

dfs 스패닝 트리에서 부모 노드 - 자손 노드 의 간선을 조사할때

 

자손이 루트인 서브트리에서 부모로 가는 간선을 제외한 역방향 간선을 조사.

 

만약 서브트리에서 역방향간선이 전부 부모노드를 거슬러 올라가지 못할 경우.

 

부모노드 -> 자손 노드 의 간선이 단절선이되어

 

이 선을 제거하면 컴포넌트가 분리된다.

부모 노드로 가는 간선을 제외해야하는 이유 =  자손 노드의 자손들이 이 부모노드와 연결될경우, 현재 부모 - 자손 노드의 간선은 단절선이 될 수 없음. =  만약 부모노드로 가는 간선을 무시안할 경우 최소는 항상 부모노드와 같거나 작은값을 가지게됨 =  따라서 단절선을 제대로 파악할 수 없게됨

3. 코드

#include <iostream>
#include <set>
#include <vector>

using namespace std;
int V, E;
vector<vector<int> > adjList;
set<pair<int, int> > answer;

int dfs(int here, int parent, vector<int>& discovered, int& visitedNum) {
    int ret = discovered[here] = visitedNum++;

    for(int i = 0; i < adjList[here].size(); i++) {
        int there = adjList[here][i];
        int subTree = discovered[there];
        if(parent == there) continue;
        if(subTree == -1) {
            subTree = dfs(there, here, discovered, visitedNum);
            if(subTree > discovered[here]) {
                int a = here, b = there;
                if(a > b) {
                    swap(a, b);
                }
                answer.insert({a, b});
            }
        }
        ret = min(ret, subTree);
    }
    return ret;
}

void dfsAll() {
    vector<int> discovered(V + 1, -1);
    int visitedNum = 0;
    for(int i = 0; i < V; i++) {
        if(discovered[i+1] == -1) {
            dfs(i+1, 0, discovered, visitedNum);
        }
    }
    cout<<answer.size()<<"\n";
    for(auto item : answer) {
        cout<<item.first<< " "<<item.second<<"\n";
    }
}
//a < b
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();
}