LeetCode 685. Redundant Connection II — C# Implementation

Problem Recap

We’re given a directed graph that was a rooted tree with one extra edge. The extra edge creates exactly one of three scenarios:

1. A node has two parents, no cycle.
2. A node has two parents, and a cycle exists.
3. No node has two parents, but a cycle exists.

Return the redundant edge (the latest one if multiple valid answers exist).

Approach: Union-Find + Parent-Edge Tracking

Phase 1 — Detect a node with two parents:

Walk through edges and record, for each child node, the index of the edge that first pointed to it. If a second edge points to the same child, save both indices as firstParentEdge and secondParentEdge.

Phase 2 — Union-Find cycle detection:

· No double-parent node → process all edges with Union-Find; the edge that connects two already-connected nodes is the answer.
· A double-parent node exists → temporarily skip secondParentEdge and run Union-Find:
· Cycle still appears → firstParentEdge is the redundant one.
· No cycle → secondParentEdge is the redundant one.

C# Code

publicclassSolution{privateint[]parent;publicint[]FindRedundantDirectedConnection(int[][]edges){intn=edges.Length;int[]parentEdge=newint[n+1];Array.Fill(parentEdge,-1);intfirstParentEdge=-1,secondParentEdge=-1;// Phase 1: find a node with two parentsfor(inti=0;i<n;i++){intv=edges[i][1];if(parentEdge[v]==-1){parentEdge[v]=i;// first edge pointing to v}else{firstParentEdge=parentEdge[v];secondParentEdge=i;break;// only one such node is possible}}// Phase 2: Union-Find cycle detectionif(firstParentEdge==-1){// Case 3: no double-parent, pure cycleInit(n);foreach(vareinedges){if(!Union(e[0],e[1]))returne;}}else{// Cases 1 & 2: a node has two parentsInit(n);for(inti=0;i<n;i++){if(i==secondParentEdge)continue;// skip candidate edgeif(!Union(edges[i][0],edges[i][1])){// Cycle remains => the earlier edge is the culpritreturnedges[firstParentEdge];}}// No cycle => the later edge is the redundant onereturnedges[secondParentEdge];}returnArray.Empty<int>();// unreachable}privatevoidInit(intn){parent=newint[n+1];for(inti=1;i<=n;i++)parent[i]=i;}privateintFind(intx){while(parent[x]!=x){parent[x]=parent[parent[x]];// path halvingx=parent[x];}returnx;}privateboolUnion(intx,inty){intrx=Find(x),ry=Find(y);if(rx==ry)returnfalse;// already connected → cycleparent[rx]=ry;returntrue;}}

Complexity

· Time: O(n · α(n)) ≈ O(n) — Union-Find with path compression.
· Space: O(n) for the parent and parentEdge arrays.

Example Walkthrough

Example 1: edges = [[1,2],[1,3],[2,3]]

· Phase 1: parentEdge[3] = 2 (index 2), no conflict → firstParentEdge = -1.
· Phase 2 (Case 3): union [1,2] ✓, [1,3] ✓, [2,3] → find(2)==find(3) → return [2,3]. ✓

Example 2: edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]

· Phase 1: parentEdge[1] = 3, no conflict.
· Phase 2 (Case 3): [4,1] closes the cycle → return [4,1]. ✓

Double-parent case (hidden): edges = [[1,2],[1,3],[2,3]]

· Phase 1: node 3 has two parents → firstParentEdge = 1, secondParentEdge = 2.
· Phase 2: skip edge index 2, process [1,2] and [1,3] — no cycle → return edges[2] = [2,3]. ✓

Key Insight

The problem decomposes into two independent checks:

1. In-degree violation — a node with two parents.
2. Cycle violation — detected via Union-Find.

Checking the double-parent candidate against the cycle gives a deterministic answer for all three scenarios in near-linear time — the standard interview solution.