[BOJ 3977]

문제 바로가기 : https://www.acmicpc.net/problem/3977
비슷한 유형 문제, BOJ 4196 : https://www.acmicpc.net/problem/4196
문제 설명은 위 링크에서 확인해주시길 바랍니다.

Solution

review

BOJ 4196에서 SCC와 위상 정렬을 함께 사용했었다. 이 문제도 비슷하다.
문제에서 다른 모든 구역에 도달할 수 있는 시작 구역이라는 표현을 썼다. SCC 개념이 이용됐다는걸 알 수 있다.
그럼 모두 1개의 SCC에 있어야 한다는 말인가? 싶지만 그렇지 않다. 다른 SCC여도 도달할 수 있다!
SCC들의 묶음으로 모아놓았을 때 SCC간의 간선이 있어야 한다. 그렇다면 무조건 degree가 0인 SCC가 발생한다.
여기서는 degree가 0인 SCC가 여러개가 되면 모든 구역에 도달할 수 없다.
따라서 degree가 0이 되는 SCC가 1개일 때 그 SCC의 속한 노드들을 출력하면 되고, 그렇지 않으면 Confused를 출력한다.

int zerodegree = 0; //1개가 아니면 confused
int wherescc = -1;
for (int i = 1; i <= sccnum; i++)
    if (degree[i] == 0) {
        zerodegree++;
        wherescc = i;
    }

if (zerodegree > 1 || wherescc == -1) {
    cout << "Confused" << '\n';
}
else {
    /*
    for (int i = 0; i < V; i++) {
        if (uni[i] == wherescc)
            cout << i << '\n';
    }
    */
    for (auto& a : SCC[wherescc - 1]) cout << a << '\n';
}
cout << '\n';

주석으로 처리한 부분은 어느 집합에 담겼는지 알려주는 배열(uni[])에서 가져와 출력하는 방식이고
그 아랫줄은 SCC를 가져와서 속한 노드를 출력하는 방식이다. 어느 방법으로 해도 답은 똑같다.