A graph is bipartite if the vertices can be partitioned into two subsets and , such that every edge has one vertex in and the other in . Describe and analyze an efficient algorithm that determines whether a given unidrected graph is bipartite.
Suppose we are given a directed acyclic graph with a unique source and a unique sink . A vertex is called an -cut vertex if every path from to passes through , or equivalently, if deleting makes unreachable from . Describe and analyze an algorithm to find every -cut vertex in .