LeetCode 685. Redundant Connection II — C# ImplementationProblem RecapWe’re given a directed graph that was a rooted tree with one extra edge. The extra edge creates exactly one of three scenarios:A node has two parents, no cycle.A node has two parents, and a cycle exists.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 TrackingPhase 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# CodepublicclassSolution{privateint[]parent;publicint[]FindRedundantDirectedConnection(int[][]edges){intnedges.Length;int[]parentEdgenewint[n1];Array.Fill(parentEdge,-1);intfirstParentEdge-1,secondParentEdge-1;// Phase 1: find a node with two parentsfor(inti0;in;i){intvedges[i][1];if(parentEdge[v]-1){parentEdge[v]i;// first edge pointing to v}else{firstParentEdgeparentEdge[v];secondParentEdgei;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(inti0;in;i){if(isecondParentEdge)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.Emptyint();// unreachable}privatevoidInit(intn){parentnewint[n1];for(inti1;in;i)parent[i]i;}privateintFind(intx){while(parent[x]!x){parent[x]parent[parent[x]];// path halvingxparent[x];}returnx;}privateboolUnion(intx,inty){intrxFind(x),ryFind(y);if(rxry)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 WalkthroughExample 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 InsightThe problem decomposes into two independent checks:In-degree violation — a node with two parents.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. 
长河君 · 2026/10/21 20:52:00 · 阅读 1.2k DeepSeek LeetCode 685. Redundant Connection II C# Implement
LeetCode 685. Redundant Connection II — C# ImplementationProblem RecapWe’re given a directed graph that was a rooted tree with one extra edge. The extra edge creates exactly one of three scenarios:A node has two parents, no cycle.A node has two parents, and a cycle exists.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 TrackingPhase 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# CodepublicclassSolution{privateint[]parent;publicint[]FindRedundantDirectedConnection(int[][]edges){intnedges.Length;int[]parentEdgenewint[n1];Array.Fill(parentEdge,-1);intfirstParentEdge-1,secondParentEdge-1;// Phase 1: find a node with two parentsfor(inti0;in;i){intvedges[i][1];if(parentEdge[v]-1){parentEdge[v]i;// first edge pointing to v}else{firstParentEdgeparentEdge[v];secondParentEdgei;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(inti0;in;i){if(isecondParentEdge)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.Emptyint();// unreachable}privatevoidInit(intn){parentnewint[n1];for(inti1;in;i)parent[i]i;}privateintFind(intx){while(parent[x]!x){parent[x]parent[parent[x]];// path halvingxparent[x];}returnx;}privateboolUnion(intx,inty){intrxFind(x),ryFind(y);if(rxry)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 WalkthroughExample 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 InsightThe problem decomposes into two independent checks:In-degree violation — a node with two parents.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.