685. Redundant Connection II

At a Glance

Topic: advanced-graphs
Pattern: Union-Find + directed-tree case analysis
Difficulty: Hard
Companies: Google, Amazon, Microsoft, Intuit, Adobe
Frequency: Medium
LeetCode: 685

Problem (one-liner)

A rooted tree on nodes 1..n gained one extra directed edge. Remove one edge so the graph becomes a valid rooted tree. If several edges work, return the one that appears last in edges.

Recognition Cues

Permutation tree + one redundant edge
Scan for two incoming edges to the same node — at most one such node
No double indegree ⇒ extra edge closes a directed cycle with indegree 1 everywhere — behave like undirected cycle detection on pairs

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute — try removing each edge and validate rooted tree — O(n^2).
Case split + UF — detect (edgeFirst, edgeSecond) to double sink; try skipping later edge first — O(n α(n)).

Optimal Solution

Go

func findRedundantDirectedConnection(edges [][]int) []int {
	nodeCount := len(edges)
	parentSlot := make([]int, nodeCount+1)
	var edgeFirst []int
	var edgeSecond []int
	for _, edge := range edges {
		from := edge[0]
		to := edge[1]
		if parentSlot[to] != 0 {
			edgeFirst = []int{parentSlot[to], to}
			edgeSecond = edge
			break
		}
		parentSlot[to] = from
	}
	if edgeFirst == nil {
		return lastEdgeInUndirectedCycle(edges)
	}
	if hasCycleIgnoringEdge(edges, edgeSecond, nodeCount) {
		return edgeFirst
	}
	return edgeSecond
}

func hasCycleIgnoringEdge(edges [][]int, skip []int, nodeCount int) bool {
	parent := make([]int, nodeCount+1)
	for node := range parent {
		parent[node] = node
	}
	var find func(int) int
	find = func(node int) int {
		for parent[node] != node {
			parent[node] = parent[parent[node]]
			node = parent[node]
		}
		return node
	}
	for _, edge := range edges {
		if edge[0] == skip[0] && edge[1] == skip[1] {
			continue
		}
		left := find(edge[0])
		right := find(edge[1])
		if left == right {
			return true
		}
		parent[right] = left
	}
	return false
}

func lastEdgeInUndirectedCycle(edges [][]int) []int {
	nodeCount := len(edges)
	parent := make([]int, nodeCount+1)
	for node := range parent {
		parent[node] = node
	}
	var find func(int) int
	find = func(node int) int {
		for parent[node] != node {
			parent[node] = parent[parent[node]]
			node = parent[node]
		}
		return node
	}
	for _, edge := range edges {
		left := find(edge[0])
		right := find(edge[1])
		if left == right {
			return edge
		}
		parent[right] = left
	}
	return nil
}

JavaScript

function findRedundantDirectedConnection(edges) {
  const nodeCount = edges.length;
  const parentSlot = new Array(nodeCount + 1).fill(0);
  let edgeFirst = null;
  let edgeSecond = null;
  for (const edge of edges) {
    const from = edge[0];
    const to = edge[1];
    if (parentSlot[to] !== 0) {
      edgeFirst = [parentSlot[to], to];
      edgeSecond = edge;
      break;
    }
    parentSlot[to] = from;
  }
  if (edgeFirst === null) {
    return lastEdgeInUndirectedCycle(edges);
  }
  if (hasCycleIgnoringEdge(edges, edgeSecond, nodeCount)) {
    return edgeFirst;
  }
  return edgeSecond;
}

function hasCycleIgnoringEdge(edges, skip, nodeCount) {
  const parent = Array.from({ length: nodeCount + 1 }, (_, index) => index);
  function find(node) {
    if (parent[node] !== node) {
      parent[node] = find(parent[node]);
    }
    return parent[node];
  }
  for (const edge of edges) {
    if (edge[0] === skip[0] && edge[1] === skip[1]) {
      continue;
    }
    const left = find(edge[0]);
    const right = find(edge[1]);
    if (left === right) {
      return true;
    }
    parent[right] = left;
  }
  return false;
}

function lastEdgeInUndirectedCycle(edges) {
  const nodeCount = edges.length;
  const parent = Array.from({ length: nodeCount + 1 }, (_, index) => index);
  function find(node) {
    if (parent[node] !== node) {
      parent[node] = find(parent[node]);
    }
    return parent[node];
  }
  for (const edge of edges) {
    const left = find(edge[0]);
    const right = find(edge[1]);
    if (left === right) {
      return edge;
    }
    parent[right] = left;
  }
  return null;
}

Track intended parent while scanning edges in order. First time to already has a parent, record first parent-edge (oldParent, to) and second incoming (from, to). If skipping the second edge leaves an undirected cycle somewhere, the redundant edge must be the first; otherwise the second (later in input) is the removable one.

If no double indegree appeared, the redundant arc completes a single cycle — union-find on pairs like problem 684 returns the last edge closing the loop.

Edge Cases

Double parent where removing second edge breaks cycle vs forest balance
Input guaranteed one redundant edge — algorithm always returns one

Pitfalls

Using directed reachability instead of undirected cycle check when testing skips
Wrong tie-break: problem wants last among valid removals — trying skip order above matches editorial logic

Variants

List all edges that could be removed — enumerate candidates from indegree list + cycle edges.
Weighted removals — choose cheapest feedback edge (minimum feedback arc set approximations).
k extra edges — feedback edge set; beyond single edge uses matroid intersection theory (not interview-core).

Mind-Map Tags

#union-find #directed-tree #two-parents #cycle-detection #case-analysis