You are given a directed graph. The graph may contain loops, and multiple edges may exist between pairs of vertices. You can merge a pair of vertices into a single vertex. When a pair of vertices is merged, outgoing and incoming edges from both vertices become outgoing and incoming edges, respectively, of the resulting vertex.
For example, consider a graph with four vertices {a, b, c, d} and three edges {a->b, c->b, c->d}. If we merge vertices b and c, the resulting graph will have three vertices {a, bc, d} and three edges {a->bc, bc->bc, bc->d}.
A graph is a cycle if its vertices can be ordered v0, v1, ..., vn-1 (where n is the total number of vertices) such that the following two properties are satisfied:
- Every edge in the graph goes from vi to v(i+1)%n.
- For all i between 0 and n-1, inclusive, there exists at least one edge that goes from vi to v(i+1)%n.
You are given a String[] adj. The ith element of adj is a space delimited list of integers representing all the outgoing edges from vertex i. Each integer represents the target vertex of an outgoing edge. Return the minimal number of merge operations necessary to convert the given graph into a cycle. If a solution doesn't exist, return the number of vertices in the given graph instead.
|