백준 11400번: 단절선 (C++)

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

11400번: 단절선

---

Solved By: Articulation

 

직전 포스팅인 Articulation Point와 접점이 많습니다. Articulation Point에서 childOrder가 현재 node의 visitedOrder보다 큰 경우가 Articulation Edge가 되는 경우입니다.

#include <iostream>
#include <vector>
#define MAX 100001
#define pii pair<int, int>
using namespace std;

vector<int> adj[MAX];
int v, e;
vector<pii> isCut;
int order = 0;

int dfs(int now, int par){
    int minOrder = visitedOrder[now] = ++order;
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        
        // parent node에 접근할 경우 continue
        if(next == par) continue;
        
        if(visitedOrder[next]){
            minOrder = min(minOrder, visitedOrder[next]);
            continue;
        }
        
        int childOrder = dfs(next, now);
        
        if(visitedOrder[now] < childOrder){
            // 아직 방문 안 한 node의 visitedOrder가 현재 node의 visitedOrder보다
            // 크다면 해당 edge는 Articulation이 된다.
            // 같다는 되지 않는 이유가 해당 edge가 없어져도 현재 node로 올 수 있는
            // edge가 있다는 뜻이다.
            isCut.push_back({min(now, next), max(now, next)});
        }
        
        minOrder = min(minOrder, childOrder);
    }
    
    return minOrder;
}

int main(){
    cin >> v >> e;
    for(int i = 0; i < e; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    for(int i = 1; i <= v; i++){
        if(!visitedOrder[i]) dfs(i, 0);
    }
}