[ 1 ]  [ 2 ]  [ 3 ]  [ 4 ]  [ 5 ]  [ 6 ]  [ 7 ] 
Programming Problems/Graph

N개의 노드에 대해 acyclic이 되는 최대 엣지의 갯수는(방향,비방향)

비방향 그래프에서는 최대 V-1 개의 엣지가 가능하다. spanning tree이다. 그 이상 연결하면 반드시 사이클이 생긴다.

방향 그래프에서는 Topological sort를 고려한다고 생각해 보면 맨 앞에서는 V-1개 , V-2 ... 1 의 총합은 V(V-1)/2 개이다.