채점 번호: 11577544 (AC) 

해당 문제는 Strongly Connected Component로 분류되어있습니다.

글이 조금 길기 때문에 읽기가 좀 부담스러우시다면 제가 제대로 적용을 또는 생각을한게 맞는지만 봐주셨으면 좋겠습니다.

간략히 요약해드리자면, 도미노가 놓여져있는데, 도미노들은 숫자 (x, y)입력으로 들어옵니다.

즉 x y 이렇게 입력이 들어온다면 x가 넘어졌을때 연결된 y 또한 넘어진다는 것이 기본 설정입니다.

따라서 입력이

x  y

y  z

z  x

이렇게 들어오면 사이클이 생성 되며 x, y, z 중 어느하나라도 넘어진다면 한번에 모든 도미노가 넘어갈 수 있기 때문에 출력값은 1이 나오게 됩니다.

물론 위의 입력에서 마지막 줄 (z  x)가 빠져도 답은 1입니다. (이는 문제의 예제와 같은 입력이라 보시면 되겠습니다.)

제가 SCC 자체를 공부한지 이제 2일정도 밖에 안돼서 알고리즘의 동작에 있어 이해가 조금 부족한것 같아 이렇게 글을 올립니다. 

코사라주 알고리즘 사용했구요. 기본적인 매커니즘은 

1. 정방향 역방향 리스트를 입력때 나눠서 받아주고
2. 정방향 리스트를 1 ~ N 까지 반복문에 dfs를 이용해서 탐색합니다.
3. 깊이 우선 탐색으로 탐색된 가장 마지막 노드 즉, 더 이상 갈 수 있는 노드가 없을 때 반환된 노드의 번호를 스택에 저장합니다. (물론 중복은 없어야합니다)
4. 이렇게 스택에 저장된 번호를 pop을 하며 그 노드 번호를 가지고 역방향 리스트로 다시 깊이 우선 탐색을 합니다.
5. '스택에서 꺼낸 노드 하나를 통해 탐색간 이동 가능한 노드라면 그 노드들은 하나의 SCC에 속한다'고 할 수 있습니다.

말을 제대로 정리해서 쓰려했는데, 이해가 되신지는 잘 모르겠습니다.

이러한 방식을 이용해 풀었는데요. 제가 정답을 받는 코드는 역방향 리스트를 사용하지 않고 스택에서 받아온 노드를 다시 정방향 리스트를 이용해서 SCC를 찾았다는 점입니다.

제가 생각하기론 도미노의 입력이 항상 사이클이 존재 할 수 없고, 

사이클이든 아니든 어떤 노드 x에서 한번에 모두 넘어뜨릴 수 있다면 그게 하나의 요소 집합이라고 생각을 하고 풀었습니다.

그렇게 생각해보니 역방향으로 들어가면 사이클이 아니면 연결된 요소들을 서로 다른 집합으로 분류 될 수 있기 때문에 정방향으로 찾아야한다는 생각이 들어서 그냥 그렇게 구현하고 그때 탐색가능한 요소들의 집합 갯수를 찾으니 AC가 떴습니다.

이게 맞는 풀이인지 혹은 TC가 부족한 것인지 궁금합니다. 읽어주셔서 감사합니다.