685. Redundant Connection II

1class Solution {
2    public int[] findRedundantDirectedConnection(int[][] edges) {
3        int numEdges = edges.length;
4        int[] parents = new int[numEdges + 1];
5        // Initialize each node to be its own parent
6        for (int i = 0; i <= numEdges; ++i) {
7            parents[i] = i;
8        }
9        UnionFind unionFind = new UnionFind(numEdges + 1);
10        int conflictEdgeIndex = -1;
11        int cycleEdgeIndex = -1;
12        for (int i = 0; i < numEdges; ++i) {
13            int from = edges[i][0], to = edges[i][1];
14            // Check if the current edge creates a conflict (i.e., a node with two parents)
15            if (parents[to] != to) {
16                conflictEdgeIndex = i;
17            } else {
18                // Set the parent of the 'to' node
19                parents[to] = from;
20                // Try to union the two nodes; if they are already connected, there is a cycle
21                if (!unionFind.union(from, to)) {
22                    cycleEdgeIndex = i;
23                }
24            }
25        }
26        if (conflictEdgeIndex == -1) {
27            // If there is no conflict, return the edge causing the cycle
28            return edges[cycleEdgeIndex];
29        }
30        int to = edges[conflictEdgeIndex][1];
31        if (cycleEdgeIndex != -1) {
32            // If there is both a conflict and a cycle, return the edge causing the conflict,
33            // which is the first one when traversing from the 'to' node
34            return new int[]{parents[to], to};
35        }
36        // If there is only a conflict, return the conflicting edge
37        return edges[conflictEdgeIndex];
38    }
39}
40
41class UnionFind {
42    private int[] parent;
43    private int count;
44
45    public UnionFind(int size) {
46        parent = new int[size];
47        for (int i = 0; i < size; ++i) {
48            parent[i] = i;
49        }
50        this.count = size;
51    }
52
53    public boolean union(int a, int b) {
54        int parentA = find(a);
55        int parentB = find(b);
56        // If 'a' and 'b' are already connected, cannot perform union operation
57        if (parentA == parentB) {
58            return false;
59        }
60        // Connect the sets by updating the parent
61        parent[parentA] = parentB;
62        --count; // Decrement the number of components in the UnionFind
63        return true;
64    }
65
66    public int find(int x) {
67        // Path compression: make paths shorter for the 'find' queries
68        if (parent[x] != x) {
69            parent[x] = find(parent[x]);
70        }
71        return parent[x];
72    }
73}
74

1#include <vector>
2#include <numeric>
3using namespace std;
4
5// Class UnionFind represents a data structure for disjoint-set operations.
6class UnionFind {
7public:
8    // p stores the parent of each element, n represents the number of elements.
9    vector<int> parent;
10    int num_sets;
11
12    // Constructor initializes a disjoint-set for n elements.
13    UnionFind(int n)
14        : num_sets(n)
15        , parent(n) {
16        // iota fills the parent vector with increasing values starting from 0,
17        // so each element is initially in its own set.
18        iota(parent.begin(), parent.end(), 0);
19    }
20
21    // Method to unite two sets. Returns true if a union was performed, else false.
22    bool unite(int a, int b) {
23        int parent_a = find(a), parent_b = find(b);
24        // If both elements have the same parent, they are already connected, so no union is performed.
25        if (parent_a == parent_b) return false;
26        // Assign one element's parent to the other, effectively merging the sets.
27        parent[parent_a] = parent_b;
28        // Decrement the count of disjoint sets.
29        --num_sets;
30        return true;
31    }
32
33    // Find method with path compression. Finds the representative of the set containing x.
34    int find(int x) {
35        if (parent[x] != x) {
36            // Recursively find the parent and perform path compression.
37            parent[x] = find(parent[x]);
38        }
39        return parent[x];
40    }
41};
42
43// Solution class contains methods to analyze the graph and find the redundant edge.
44class Solution {
45public:
46    // Method to find the redundant directed connection in a graph represented by the edges list.
47    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
48        int num_edges = edges.size();
49        // p keeps track of direct parents for each node.
50        vector<int> direct_parents(num_edges + 1);
51        for (int i = 0; i <= num_edges; ++i) direct_parents[i] = i;
52        UnionFind uf(num_edges + 1);
53        int conflict_edge_idx = -1, cycle_edge_idx = -1;
54
55        // Iterate over the edges to find any cycle or conflict.
56        for (int i = 0; i < num_edges; ++i) {
57            int u = edges[i][0], v = edges[i][1];
58            // If v already has a parent, we have found a conflict.
59            if (direct_parents[v] != v) {
60                conflict_edge_idx = i;
61            } else {
62                // Assign parent for v.
63                direct_parents[v] = u;
64                // If the union operation indicates a cycle, record the current edge index.
65                if (!uf.unite(u, v)) {
66                    cycle_edge_idx = i;
67                }
68            }
69        }
70
71        // If there's no conflict, the redundant connection must be part of a cycle.
72        if (conflict_edge_idx == -1) {
73            return edges[cycle_edge_idx];
74        }
75
76        // If a cycle exists when a conflict is found, we return the previous edge that caused the cycle with the conflicting node.
77        int v = edges[conflict_edge_idx][1];
78        if (cycle_edge_idx != -1) {
79            return {direct_parents[v], v};
80        }
81        // If there's only a conflict without a cycle, we return the conflicting edge.
82        return edges[conflict_edge_idx];
83    }
84};
85

1// Importing array manipulations from lodash for `fill` similar to `iota` in C++
2import * as _ from "lodash";
3
4// Store the parent of each element; n represents the number of elements.
5let parent: number[];
6let numSets: number;
7
8// Initialize a disjoint-set for n elements.
9function initializeUnionFind(n: number): void {
10    numSets = n;
11    parent = _.fill(Array(n), 0).map((_, index) => index);
12}
13
14// Unite two sets. Returns true if a union was performed, otherwise false.
15function unite(a: number, b: number): boolean {
16    let parentA = find(a), parentB = find(b);
17    if (parentA == parentB) return false;
18    parent[parentA] = parentB;
19    numSets--;
20    return true;
21}
22
23// Find with path compression. Finds the representative of the set containing x.
24function find(x: number): number {
25    // Base case: if the element's parent is itself, it is the representative.
26    if (parent[x] != x) {
27        // Recursively find the parent and perform path compression.
28        parent[x] = find(parent[x]);
29    }
30    return parent[x];
31}
32
33// Find the redundant directed connection in a graph represented by the edges list.
34function findRedundantDirectedConnection(edges: number[][]): number[] {
35    // Variables to keep track of the state during the analysis.
36    let numEdges = edges.length;
37    let directParents: number[] = _.fill(Array(numEdges + 1), 0).map((_, index) => index);
38    initializeUnionFind(numEdges + 1);
39    let conflictEdgeIdx: number = -1, cycleEdgeIdx: number = -1;
40
41    // Iterate over the edges to find any cycle or conflict.
42    edges.forEach(([u, v], idx) => {
43        // If v already has a parent, a conflict is found.
44        if (directParents[v] != v) {
45            conflictEdgeIdx = idx;
46        } else {
47            // Assign the direct parent for v.
48            directParents[v] = u;
49            // If the union operation indicates a cycle, record the current edge index.
50            if (!unite(u, v)) {
51                cycleEdgeIdx = idx;
52            }
53        }
54    });
55
56    // If no conflict, the redundant connection is part of a cycle.
57    if (conflictEdgeIdx == -1) {
58        return edges[cycleEdgeIdx];
59    }
60
61    // If a cycle exists when a conflict is found, return the edge creating the cycle with the conflicting node.
62    let conflictV = edges[conflictEdgeIdx][1];
63    if (cycleEdgeIdx != -1) {
64        return [directParents[conflictV], conflictV];
65    }
66
67    // If there's only a conflict without a cycle, return the conflicting edge.
68    return edges[conflictEdgeIdx];
69}
70
71// Example Usage:
72const edges = [[1,2], [1,3], [2,3]];
73const redundantEdge = findRedundantDirectedConnection(edges);
74console.log(redundantEdge); // Output will be the redundant edge from the input graph.
75