Page 1 of 1
VI. (15 points) A directed graph G = (V, E) is said to be half-connected if, for all pairs of vertices u, u EV, either t
Posted: Mon Jun 06, 2022 6:32 pm
by answerhappygod
- Vi 15 Points A Directed Graph G V E Is Said To Be Half Connected If For All Pairs Of Vertices U U Ev Either T 1 (27.8 KiB) Viewed 30 times
VI. (15 points) A directed graph G = (V, E) is said to be half-connected if, for all pairs of vertices u, u EV, either there is a directed path from u to v or there is a directed path from v to u, or both. Give an O(n + m)-time algorithm to determine whether or not a di- rected graph G with n vertices and m edges is half-connected. (Hint. Construct first the directed acyclic graph whose vertices are the strongly- connected components of G.)