Algorithm - Cut Vertex(단절점)

개념

단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다.

---

작동원리

DFS를 이용하여 정점이 몇 번째로 방문되는지 기록하고, 기록한 값 중에 최솟값을 반환한다.

 

- DFS를 시작한 Root일 경우

DFS를 통해 갈 수 있는 정점이 2개 이상일 경우 단절점이다.

(Root를 통해 갈 수 있다는 정점이 2개 이상이면 Root를 제거했을 때 그래프가 2개 이상으로 분리된다는 뜻이다.)

 

- DFS를 시작한 Root가 아닐 경우

DFS를 통해 반환된 값들 중 자신보다 크거나 같은게 있으면 단절점이다.

(자신보다 값이 크거나 같은게 있다면, 아직 DFS를 통해 방문하지 않은 정점이 있다는 뜻이고, 자신이 없을 경우 방문하지 못하기 때문에 그래프가 분리된다는 뜻이다.)

---

시간복잡도

DFS를 사용할 때 O(V + E)

---

문제

11266 단절점

www.acmicpc.net/problem/11266

11266번: 단절점

---

코드

#include <bits/stdc++.h>
using namespace std;

constexpr int NONE = -1;

int order = 0;
vector<int> isVisited;
vector<bool> isAnswer;
vector<vector<int>> graph;
int dfs(int index, bool isRoot) {
    isVisited[index] = order++;

    int count = 0;
    int result = isVisited[index];
    for (int &next : graph[index]) {
        if (isVisited[next] == NONE) {
            count++;
            int low = dfs(next, false);

            if (!isRoot && isVisited[index] <= low) {
                isAnswer[index] = true;
            }
            
            result = min(result, low);
        } else {
            result = min(result, isVisited[next]);
        }
    }

    if (isRoot) {
        isAnswer[index] = count >= 2;
    }

    return result;
}

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

    int v, e;
    cin >> v >> e;

    graph.resize(v + 1);
    while (e--) {
        int v1, v2;
        cin >> v1 >> v2;

        graph[v1].push_back(v2);
        graph[v2].push_back(v1);
    }


    isVisited.resize(v + 1, NONE);
    isAnswer.resize(v + 1, false);
    for (int i = 1;i <= v;++i) {
        if (isVisited[i] == NONE) {
            dfs(i, true);
        }
    }

    cout << count(isAnswer.begin(), isAnswer.end(), true) << "\n";
    for (int i = 1;i <= v;++i) {
        if (isAnswer[i]) {
            cout << i << " ";
        }
    }
}