다리 찾기 알고리즘을 다음과 같이 구현해보았습니다.
~~~c++
vector > 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스패닝트리 상에서 부모로 가는 간선을 무시하며 역방향 간선을 찾는 방법으로 구현했습니다. 그런데 이것이 적절한지 확인할 방법이 없네요. 도움이 필요합니다. 잘못된 점이 있다면 어느 부분이 잘못되었는지와 이를 개선한 코드를 알고 싶습니다.ㅜㅜ 꼭 답변 부탁드립니다~~~~^
의도하신 방법대로 내지는 책에 설명된 방법대로 코드는 잘 작성하신 것으로 보입니다. 연습문제를 풀어 한 번 확인해보시면 좋을 것 같습니다.
사족을 붙이자면 정답을 저장한 자료구조를 왜 맵의 벡터로 만드셨는지 잘 추측이 안 가네요.. 정수 벡터의 벡터라든가, 간단히 페어의 벡터로 브리지만 저장했어도 될 것 같습니다.
dkwkekzz
안녕하세요.
일단 제 질문을 읽어주셔서 감사합니다.
알고리즘 전략 교재 p.857 관련 질문입니다.
다리 찾기 알고리즘을 다음과 같이 구현해보았습니다. > isBridge;
~~~c++
vector
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스패닝트리 상에서 부모로 가는 간선을 무시하며 역방향 간선을 찾는 방법으로 구현했습니다. 그런데 이것이 적절한지 확인할 방법이 없네요. 도움이 필요합니다. 잘못된 점이 있다면 어느 부분이 잘못되었는지와 이를 개선한 코드를 알고 싶습니다.ㅜㅜ 꼭 답변 부탁드립니다~~~~^
9년 전