백준 3977번 축구 전술

사용한 알고리즘 : SCC

​

문제는 각 점들을 SCC로 묶었을 때, indegree가 0인 (들어오는 edge가 없는) SCC가 딱 1개 있는지 여부였습니다. (2개 있다면 서로는 서로에게 못가니, 한 지점에서 다른 모든 지점으로 갈 수 있는지 묻는 물음에 부합하지 못합니다.)

​

우선 각 점들을 SCC로 묶었습니다.

이후 모든 점들을 돌면서, 그 점의 자식이 자신과 다른 SCC 에 있는지 확인하고,

만약 다른 SCC에 있는 경우, 자식이 속한 SCC의 indegree++ 해주었습니다.

이후 SCC를 모아놓은 벡터를 돌며 indegree가 0 인 SCC가 1개인지 확인 후,

1개인 경우 답을 말하고,

아닌 경우 "Confused"를 외쳐주었습니다.

​