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

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

11266번: 단절점

---

Solved By: Articulation

 

Articulation 구현에 대해 아쉬운 점이 한 가지 있었습니다. 바로 minOrder 부분이 이해가 되지 않는 것이었는데

minOrder를 주석에 달아두었듯이

'Now Node의 *Child Node로써 갈 수 있는 Node* 중 가장 일찍 방문한 Node'라고 생각하면 쉽습니다.

(이 말도 100% 이해를 하기에는 애매한 말이기는 합니다.)

 

(이렇게 인지한 부분이 바뀌면서 기존의 변수명이 childOrder였던 변수가 childMinOrder로 변경되었습니다.)

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

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

// minOrder = Now Node의 *child Node가 갈 수 있는 Node* 중 가장 일찍 방문한 Node

// Now Node의 Child Node가 갈 수 있는 Node라는 점을 인지하여
// Now Node를 지나가지 않는 Node 중 가장 일찍 방문한 Node라고 생각하면 쉽다.
// == Child Node

// Child Node이기 때문에 Now Node를 돌아가서 더 빠르게 방문한 Node가 존재할 수 있는 것이다.

int dfs(int now, bool isRoot){
    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]){
            minOrder = min(minOrder, visitedOrder[next]);
            continue;
        }
        
        child++;
        
        int childMinOrder = dfs(next, false);
        
        if(!isRoot && visitedOrder[now] <= childMinOrder){
            isCut[now] = true;
        }
        
        minOrder = min(minOrder, childMinOrder);
    }
    
    if(isRoot){
        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);
    }
    
    for(int i = 1; i <= v; i++){
        if(!visitedOrder[i]){
            dfs(i, true);
        }
    }
    
    int res = 0;
    for(int i = 1; i <= v; i++){
        if(isCut[i]) res++;
    }
    
    cout << res << '\n';
    for(int i = 1; i <= v; i++){
        if(isCut[i]) cout << i << ' ';
    }
}