TopCoder problem "MergingGraph" used in SRM 321 (Division I Level Three)

Problem Statement


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.



Method signature:int distanceToCycle(String[] adj)
(be sure your method is public)


-adj will contain between 1 and 50 elements, inclusive.
-Each element of adj will contain between 0 and 50 characters, inclusive.
-Each element of adj will be a single space separated list of integers.
-Each number in each element of adj will be between 0 and (n - 1) inclusive, where n is the number of elements in adj.
-Each number in each element of adj will contain no leading zeroes.


{"1 1", "2", "0 0 0"}
Returns: 0
This graph is already a cycle.
{"0 1 1", "2", "0 0 0"}
Returns: 2
The resulting cycle is a loop.
{"1", "", "3", ""}
Returns: 2
The resulting cycle has 2 vertices.
{"2", "5 4", "", "0", "0", "0 0"}
Returns: 3

Problem url:

Problem stats url:


Mike Mirzayanov


PabloGilberto , brett1479 , Olexiy , lovro

Problem categories:

Dynamic Programming, Graph Theory