[백준 11400] 단절선

 

 그래프 이론 문제다. 예전에 풀었던 단절점 문제와 상당히 유사한 형태로 풀 수 있고, 오히려 예외 처리할 부분이 더 적어서 심플하다.
[백준 11266] 단절점

[백준 11266] 단절점

 DFS Spanning Tree를 구축하고, 이를 통해 자식 노드가 부모 노드의 조상 노드로 향할 수 있는지 판별하는 게 전부다.

 DFS를 통해 노드들을 탐색하면서 발견 순서를 저장해뒀다가, 모든 자식에 대해 부모 노드를 거치지 않고 도달할 수 있는 조상 노드를 확인한다. 만약 자식이 도달한 조상 노드가 부모의 조상 노드라면, 부모 노드와 부모 노드의 부모 노드 사이에 연결된 간선은 단절선이 될 수 없고, 자식이 도달한 조상 노드가 부모 노드 이하의 노드라면, 부모 노드와 부모 노드 사이에 연결된 간선은 단절선이다. 이때 노드의 상하관계는 탐색 중에 채워 나가는 발견 순서 배열을 통해 쉽게 확인할 수 있다.

 

 문제에서 그래프는 항상 연결되어 있음을 보장하고 있으므로 1회의 DFS로 충분하다.

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

using namespace std;

int v, e;
vector<vector<int> > graph; 
vector<int> discover;
set<pair<int, int> > answers;

int dfs(int depth, int curNode, int parent) {
    discover[curNode] = depth;

    int childMinDiscover = depth+1;

    for(auto adj: graph[curNode]) {
        if(adj!=parent) {
            if(discover[adj]==-1) {
                childMinDiscover = min(childMinDiscover, dfs(depth+1, adj, curNode));
            } else {
                childMinDiscover = min(childMinDiscover, discover[adj]);
            }
        }
    }

    if(childMinDiscover >= depth && curNode != 1) {
        answers.insert({min(curNode, parent), max(curNode, parent)});
    }

    return childMinDiscover;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> v >> e;
    graph = vector<vector<int> >(v+1, vector<int>());
    discover = vector<int>(v+1, -1);

    int a, b;
    for(int i=0; i<e; i++) {
        cin >> a >> b;
        
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    dfs(0, 1, 1);
    cout << answers.size() << "\n";
    for(auto ans: answers) {
        cout << ans.first << " " << ans.second << "\n";
    }
}