- 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 29 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 t
-
answerhappygod
- Site Admin
- Posts: 899603
- Joined: Mon Aug 02, 2021 8:13 am
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
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.)