백준 11266번: 단절점 (C++)

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

11266번: 단절점

---

Solved By: Articulation

 

처음으로 풀어본 Articulation 문제였습니다. Articulation을 찾는 방법을 설명합니다.

 

[Solution]

1) DFS를 사용하여 모든 node들의 방문 순서(visitedOrder)를 매깁니다.

2) 특정 A node에서 child node들이 A node를 거치지 않고, A node보다 빠른 visitedOrder를 가진 node로 갈 수 없다면 Articulation으로 판단합니다.

 

[Exception]

Articulation에는 예외가 존재합니다. A node가 root node일 때, child node가 2개 이상이라면 A node는 무조건 Articulation입니다.

 

 

#include <iostream>
#include <vector>
#define MAX 10001
using namespace std;

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

int dfs(int now, bool isRoot){
    // minOrder == parent node의 visitedOrder
    int minOrder = visitedOrder[now] = ++order;
    int child = 0;
    
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        
        if(visitedOrder[next]){
            // 이미 order가 있다는 것은 탐색된 정점이라면,
            // minOrder를 가져온다.
            minOrder = min(visitedOrder[next], minOrder);
            continue;
        }
        
        child++;
        
        int childOrder = dfs(next, false);
        
        if(!isRoot && visitedOrder[now] <= childOrder){
            // 해당 Node가 Root가 아니고, 탐색된 정점들 중
            // visitedOrder가 now의 vistedOrder보다 빠른 게 없다면
            // Articulation이라고 판단한다.
            isCut[now] = true;
        }
        
        minOrder = min(minOrder, childOrder);
    }
    
    cout << "node: " << now << " minOrder: " << minOrder << '\n';
    if(isRoot){
        // Root Node이고, child node가 2개 이상이라면 Articulation으로 판단
        isCut[now] = (child >= 2);
    }
    
    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);
    }
    
    // 하나의 component로 이루어지지 않았을 수도 있으므로
    // 모든 정점을 방문하여 visitedOrder가 매겨졌는지 확인한다.
    for(int i = 1; i <= v; i++){
        if(!visitedOrder[i]){
            dfs(i, true);
        }
    }
    
    int cnt = 0;
    for(int i = 1; i <= v; i++){
        if(isCut[i]) cnt++;
    }
    
    cout << cnt << '\n';
    for(int i = 1; i <= v; i++){
        if(isCut[i]) cout << i << ' ';
    }
    
    return 0;
}