제가 구현한 방법은 다음과 같습니다.

그래프 g에 대해 1번 정점을 루트로 하는 DFS 스패닝 트리를 만들면서 started에 각 정점의 방문 순서에 따라 번호를 다시 매기고 finished에는 각 정점을 루트로 하는 서브트리의 정점들 중 마지막으로 방문하는 정점을 저장, highest에는 각 정점이 역방향 간선을 타고 최대로 올라갈 수 있는 정점을 저장했습니다.

또한 각 정점이 단절점인지 미리 저장해 놓고, 각 정점마다 map<int, bool> sub에 자신을 절단한다면 분할되는 집합과 그 집합들이 역방향 간선을 타고 자신보다 높이 올라갈 수 있는지를 저장했습니다. (lower_bound가 같다면 둘은 같은 집합에 속해 있습니다.)

1번 질문에 대해서는 만약 (d,e)가 단절선이 아니라면 항상 yes이고, 단절선이라면 d와 e 중에 자식인 정점을 기준으로 두 개의 집합으로 분할되니 만약 b와 c가 같은 집합에 있다면 yes, 다른 집합에 있다면 no를 출력합니다.

2번 질문에 대해서는 만약 d가 단절점이 아니라면 항상 yes이고, 단절점이라면 둘이 같은 집합에 속해 있거나 둘 다 d보다 높은 위치에서 만날 수 있다면 yes, 아니라면 no를 출력합니다.

참고로 이 코드는 V=100000, E=500000, Q=300000인 케이스에 대해서 시간 내로 작동했지만 백준에서는 22%에서 틀렸습니다를 받았습니다.

뭔가 예외 처리를 제대로 못 한 것 같아서 5시간 넘게 붙잡고 있었는데 결국 못 찾았네요 ㅠㅠㅠㅠ

그리고 두 번째로 이해가 되지 않는 부분이 있습니다.

http://hsin.hr/2007/index.html

여기에서 대회 당시 테스트케이스를 받아서 전부 넣어봤는데요

10번 테스트케이스인 N=100000, E=500000인 케이스에 대해서는 DFS() 10만 스택까지 문제 없이 잘 돌아가는데

6번 테스트케이스인 N=50000, E=313123인 케이스는 더 작은 케이스임에도 DFS() 2만 스택 정도에 스택 오버플로우를 띄우는 이유를 잘 모르겠습니다.

이것도 알려주시면 감사합니다!