[BOJ] 3682번: Proving Equivalences

https://www.acmicpc.net/problem/3682

일단 SCC로 먼저 처리를 해 DAG를 만들어놓고 생각을 해봅시다. SCC가 단 1개인 경우는 따로 예외 처리를 해두고 나면, 주어진 DAG graph에서 in이 0개인 node는 다른 어떤 증명들로부터 imply될 수 없고, 또 out이 0개인 node는 자기자신으로부터 다른 증명을 imply할 수 없으니 in이 0개인 node와 out이 0개인 node가 없어야 합니다. 그 다음으로 생각해볼 점은 in이 0개인 node와 out이 0개인 node가 없어졌다고 했을 때 전부 equivalent가 됨이 보장되는가인데, 임의의 in이 0개인 node와 out이 0개인 node를 연결했을 때 해당 두 node는 equivalent가 되므로 max(in이 0개인 node의 갯수, out이 0개인 node의 갯수)가 정답이 됩니다.

https://github.com/blisstoner/BOJ/blob/master/3682.cpp