저는 맞는 풀이인 것 같은데요, 어떤 부분이 잘못되었다고 생각하신건가요?

저는 이 문제가 타잔 혹은 코사라주 알고리즘을 이용해 SCC 그룹을 만들고,

SCC그룹간의 간선을 파악하여 수동으로 쓰러뜨려야만 하는 SCC그룹의 갯수를 구하는 것이 정석이라고 생각합니다.

즉, indegree가 0인 SCC그룹의 갯수를 출력하는 것이 문제의 정답이 되는 셈인데, 제 코드는 단순히 역방향 탐색 시에 ans의 갯수를 증가시키고 있습니다.

물론, 제가 적은 코드가 우연히 정답을 도출하는 정확한 방법이었을수도 있지만, 저는 잘 이해가 안되서 질문을 올렸습니다.

원래 코사라주 알고리즘은 역방향 그래프에 대해서 dfs를 돌려서 post number ordering을 해주고, post number가 큰 순서대로 보면서 sink에 대해서 정방향 dfs를 돌려서 SCC 를 만드는 알고리즘입니다. 질문자분께서는 정방향 dfs를 돌려서 post number에 따라 스택에 정점을 집어넣었고, 그렇게 되면 스택의 맨 위에는 source(indegree == 0) 인 정점이 담기게 됩니다. 따라서 스택의 위에서부터 보면서 방문되지 않은 정점에 대해서 dfs를 돌리면, 아직 방문되지 않은 정점은 반드시 source 입니다.

이 문제는 명시적으로 SCC를 파악할 필요 없이 source의 개수만 세면 되므로 오히려 해당 방법이 더 맞는 풀이라고 생각합니다.

역방향 dfs할 때, rev_edges를 사용하지 않고 그냥 edges를 사용해서 정답이 나온 것 같습니다.

rev_edges를 사용하면 문제의 테스트케이스에서도 scc가 3개라 틀릴 것 같습니다.

edges를 사용할 때 정답이 나오는 이유는 저도 지식이 부족해 정확히는 잘 모르겠지만 대충 추측해보자면

정방향 dfs에서 임의의 scc에 대해 선행하여 넘어뜨려야하는 indegree가 더 작은 scc가 스택에서 무조건 나중에 쌓이게 됩니다.

그러면 연결되어 있는 scc들끼리의 집합을 x라 했을 때, x중에 가장 먼저 넘어뜨려야 하는 indegree가 0인 scc가 x중에 스택에서 가장 위에 쌓이게 되고, 

스택에 쌓인 순서대로 정방향 dfs를 한번 더 하면 x에서 indegree가 0인 scc부터 탐색하므로, x안의 모든 scc를 탐색하게 되면서 정답이 나오게 되는 것 같습니다.