GATE CSE Graph Algorithms & P/NP Completeness – Algorithms Practice Test | Set 1

Let T be an MST of a connected graph. If all edge weights are distinct, which statement is true?

In a directed graph, contracting each strongly connected component produces a graph that is always:

For a directed graph with E edges stored in adjacency lists, the transpose graph can be constructed in:

In a flow network, if an edge (u,v) carries flow f(u,v), its residual network contains a reverse edge (v,u) with residual capacity:

If a flow f is feasible and an s-t cut has capacity equal to |f|, then f is: