참고 사이트 : www.geeksforgeeks.org/determine-whether-universal-sink-exists-directed-graph/ introduction to algorithm 책의 22장 그래프 22.1_6번 문제이다. 방향 그래프 G에 대해 인접 행렬이 주어졌을 때, universal sink(진입차수가 [v]-1이고, 진출차수가 0인 노드)의 존재여부를 O(n)에 판단하는지 여부를 보이는 문제인데 인접행렬의 시간복잡도가 O(n^2)인 반면 , O(n)에 해결해야 하기 때문에 모든 edge의 정보를 다 봐서는 해결할 수 없다. 인접행렬의 한 성분 a[i][j]의 값이 0이면, j의 indegree가 [v}-1 보다 작아지므로, j번 노드가 sink가 아님을 알 수 있다. 반대..