글 읽기 - 단절점 알고리즘 루트 처리 관련해서 질문 드립니다.

mung3477 2년 전 0

안녕하세요. 우선 읽어주셔서 감사합니다.

단절점 알고리즘은 이해는 다 했는데요.

DFS를 시킬 때 어차피 루트에서도 DFS를 하고, 루트의 children이 가져오는 "닿을 수 있는 가장 높은 부모 노드의 DFS 방문 번호"는 결국 DFS 진입점인 루트보다 작을 수 밖에 없다고 생각했습니다. 따라서 루트 케이스를 맨 마지막에 따로 계산하지 않았는데요.

또한 이미 그래프를 구성하면서 DFS를 하면서 "루트"로 지정된 노드에 연결된 간선의 개수를 알 수 있고, 그 노드가 루트가 되면 연결된 간선은 곧 child의 수가 되니까 이걸로 "루트 노드는 간선이 2개 이상인 경우 단절점이다"를 판별할 수 있다고 생각했습니다.

어디가 틀렸을까요?

#include <iostream>
#include <list>
#include <set>
#include <algorithm>
using std::cin;
using std::cout;
using std::list;
using std::set;

bool *visited;
int V, *DFSNum;
list<int> *graph;
set<int> ArticulationPoints;

int DFS(int cur, int root, int& curNum);
int min(int a, int b) {
    if (a < b) return a;
    else return b;
}

int main(void) {
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int E, from, to, curNum = 1;
    cin >> V >> E;

    // create given graph
    graph = new list<int>[V + 1]{};
    for (int i = 1; i <= E; i++) {
        cin >> from >> to;
        graph[from].push_back(to);
        graph[to].push_back(from);
    }

    // make DFS tree
    visited = new bool[V + 1]{};
    DFSNum = new int[V + 1]{};
    for (int i = 1; i <= V; i++) {
        if (!visited[i]) DFS(i, i, curNum);
    }

    cout << ArticulationPoints.size() << "\n";
    for (const int& data : ArticulationPoints) {
        cout << data << " ";
    }

    ArticulationPoints.clear();
    for (int i = 1; i <= V; i++) graph[i].clear();
    delete[] graph, visited, DFSNum;
    
    return 0;
}


int DFS(int cur, int root, int& curNum) {
    int highestReachable = curNum;
    visited[cur] = true;
    DFSNum[cur] = curNum++;

    for (int next : graph[cur]) {
        if (visited[next]) {
            highestReachable = min(highestReachable, DFSNum[next]);
            continue;
        }

        int childHighestReachable = DFS(next, root, curNum);
        
        /** 
         * Articulation point detect criteria :
         * 1. child's highest reachable point is me
         * 2. if current node is root, it should have at least 2 children
         * 
         * 이 if문이 문제가 되는 부분입니다!
        */
        if ((childHighestReachable == DFSNum[cur]) && (cur != root || (cur == root && graph[cur].size() > 1))) {
            ArticulationPoints.insert(cur);
        }
        highestReachable = min(highestReachable, childHighestReachable);
    }

    return highestReachable;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

단절점 알고리즘 루트 처리 관련해서 질문 드립니다.

mung3477 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말