685. Redundant Connection II #

Problem #

In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.

The given input is a directed graph that started as a rooted tree with N nodes (with distinct values 1, 2, …, N), with one additional directed edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] that represents a directed edge connecting nodes u and v, where u is a parent of child v.

Return an edge that can be removed so that the resulting graph is a rooted tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.

Example 1:

Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given directed graph will be like this:
  1
 / \
v   v
2-->3

Example 2:

Input: [[1,2], [2,3], [3,4], [4,1], [1,5]]
Output: [4,1]
Explanation: The given directed graph will be like this:
5 <- 1 -> 2
     ^    |
     |    v
     4 <- 3

Note:

The size of the input 2D-array will be between 3 and 1000.
Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

Problem Summary #

In this problem, a rooted tree refers to a directed graph that satisfies the following conditions. The tree has exactly one root node, and all other nodes are descendants of this root node. Every node has exactly one parent, except for the root node, which has no parent. The input is a directed graph formed from a tree with N nodes (node values are distinct: 1, 2, …, N) plus one additional edge. The two vertices of the additional edge are included between 1 and N, and this additional edge does not belong to any edge that already existed in the tree. The resulting graph is a 2D array composed of edges. Each edge element is a pair [u, v], representing an edge in the directed graph connecting vertex u and vertex v, where parent node u is a parent of child node v. Return an edge that can be removed so that the remaining graph is a rooted tree with N nodes. If there are multiple answers, return the answer that appears last in the given 2D array.

Note:

The size of the 2D array is in the range from 3 to 1000.
Each integer in the 2D array is between 1 and N, where N is the size of the 2D array.

Solution Approach #

This problem is an enhanced version of Problem 684. The graph in Problem 684 is an undirected graph, while the graph in this problem is a directed graph.
The solution to this problem also uses Union-Find, but it needs to be a bit more flexible and should not use a template, because in the template, path compression and rank() optimization exist, and these optimizations will change the original direction of directed edges. So Union-Find only needs to record parent().

Through analysis, we can obtain the above 3 cases, where the red edge is the one we should actually delete. First look at Case 2 and Case 3. While continuously performing union(), after adding an edge, if it makes a node’s indegree become 2, record these two edges as candidate1 and candidate2. Put aside the later-added edge candidate2 first, and continue to union() downward. If candidate2 is the red edge, then after merging to the end, no exception will occur, so candidate2 is the red edge, meaning the edge to delete has been found. If a cycle problem occurs after merging to the end, that means candidate2 is the black edge and candidate1 is the red edge, so candidate1 is the edge to delete.
Now look at Case 1. If merging proceeds all the way to the end and no node with indegree 2 is found, it means Case 1 has been encountered. In Case 1, a cycle will occur. The problem states that if an edge needs to be deleted, delete the one that appears last. See the code comments for the specific implementation.

Code #


package leetcode

func findRedundantDirectedConnection(edges [][]int) []int {
	if len(edges) == 0 {
		return []int{}
	}
	parent, candidate1, candidate2 := make([]int, len(edges)+1), []int{}, []int{}
	for _, edge := range edges {
		if parent[edge[1]] == 0 {
			parent[edge[1]] = edge[0]
		} else { // If a node already has a parent, it means its indegree is already 1; with another edge, its indegree becomes 2, so skip this new edge candidate2 and record the edge candidate1 that conflicts with it
			candidate1 = append(candidate1, parent[edge[1]])
			candidate1 = append(candidate1, edge[1])
			candidate2 = append(candidate2, edge[0])
			candidate2 = append(candidate2, edge[1])
			edge[1] = 0 // Make a mark so that this edge can be skipped directly when it is scanned later
		}
	}
	for i := 1; i <= len(edges); i++ {
		parent[i] = i
	}
	for _, edge := range edges {
		if edge[1] == 0 { // Skip the edge candidate2
			continue
		}
		u, v := edge[0], edge[1]
		pu := findRoot(&parent, u)
		if pu == v { // A cycle is found
			if len(candidate1) == 0 { // If no indegree-2 case occurred, this corresponds to Case 1, so delete this edge
				return edge
			}
			return candidate1 // A cycle occurs and there is an indegree-2 case, indicating that candidate1 is the answer
		}
		parent[v] = pu // No cycle is found, continue merging
	}
	return candidate2 // If nothing happens in the end, candidate2 is the answer
}

func findRoot(parent *[]int, k int) int {
	if (*parent)[k] != k {
		(*parent)[k] = findRoot(parent, (*parent)[k])
	}
	return (*parent)[k]
}