다리 찾기 질문입니다.

  • dkwkekzz
    dkwkekzz

    안녕하세요.

    일단 제 질문을 읽어주셔서 감사합니다.

    알고리즘 전략 교재 p.857 관련 질문입니다.

    다리 찾기 알고리즘을 다음과 같이 구현해보았습니다.

    vector<map<int, int> > isBridge;
int findBridge(int here){
    int ret = discovered[here] = ++counter;
    for (int i = 0; i < adj[here].size(); i++){
        int there = adj[here][i];
        if (parent[here] == there) continue;
        if (discovered[there] == -1) {
            parent[there] = here;
            int subtree = findBridge(there);
            if (subtree > discovered[here]){
                isBridge[here].insert(make_pair(there, 1));
                isBridge[there].insert(make_pair(here, 1));
            }
            ret = min(ret, subtree);
        }
        else ret = min(ret, discovered[there]);
    }
    return ret;
}

    DFS스패닝트리 상에서 부모로 가는 간선을 무시하며 역방향 간선을 찾는 방법으로 구현했습니다. 그런데 이것이 적절한지 확인할 방법이 없네요. 도움이 필요합니다. 잘못된 점이 있다면 어느 부분이 잘못되었는지와 이를 개선한 코드를 알고 싶습니다.ㅜㅜ 꼭 답변 부탁드립니다~~~~^^


    7년 전
1개의 댓글이 있습니다.
  • Arine
    Arine

    의도하신 방법대로 내지는 책에 설명된 방법대로 코드는 잘 작성하신 것으로 보입니다. 연습문제를 풀어 한 번 확인해보시면 좋을 것 같습니다.
    사족을 붙이자면 정답을 저장한 자료구조를 왜 맵의 벡터로 만드셨는지 잘 추측이 안 가네요.. 정수 벡터의 벡터라든가, 간단히 페어의 벡터로 브리지만 저장했어도 될 것 같습니다.


    7년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.