sk7755   6년 전

제가 한 방법은 한점한점 dfs로 돌려서, 첫 정점과 강한연결된 정점과 그렇지 않은 점을 구분하고자 하였습니다.

visit 배열에 2로 저장된다면 그 점은 첫정점과 강하게 연결된 점일것이며, 1로 저장된다면 첫정점에서 그 점으로 밖에 경로가 없다는 것을 의미합니다.

만약 점 v1에서 dfs를 돌려 dfs가 끝났다면, visit배열에 v1과 강하게 연결된 정점 (visit = 2) 약하게 연결된 정점(visit = 1)이 저장되어있을것입니다.

v1과 강하게 연결된 정점이라면 v1과 방문한 정점개수가 같을 것이므로 방문시키지 않고 flag 배열에 방문한 정점 개수를 넣고 방문하지 않도록 했습니다.

v1과 약하게 연결된 정점이라면 당연히 v1에서 방문한 정점개수보다 작을 것이므로 flag 배열에 -1을 넣고 방문하지 않도록 했습니다.

마지막엔 flag배열에 저장된 수로 정답을 측정했습니다.


제가 코드를 제출해보니 이 코드는 20퍼센트에서 틀렸다고 나옵니다.

그러나 약하게 연결된 정점도 빠뜨리지않고 전부 dfs로 돌려보니 맞습니다가 나옵니다.

제 생각으로는 v1과 강하게 연결된 정점을 전부 캐치하지 못하고 일부만 캐치하는것 같습니다.

저 dfs 코드로는 v1과 강하게 연결된 정점을 전부 캐치하지 못하는건가요??

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