algoadvance

Leetcode 684. Redundant Connection

Problem Statement

In this problem, we are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The extra edge can be any edge that connects two previously connected nodes in the tree, thus forming a cycle. Our task is to find and return the redundant edge that can be removed to make the graph a tree of n nodes.

Formally, the graph is represented by a 2D-array of edges. Each element of edges is a pair [u, v] that represents an undirected edge connecting nodes u and v.

We need to implement a function vector<int> findRedundantConnection(vector<vector<int>>& edges) that returns the redundant edge that can be removed.

Clarifying Questions

  1. Input Constraints:
    • Can we assume that the input graph will indeed contain exactly one cycle due to one additional edge?
      • Yes, the problem guarantees one redundant connection will form one cycle.
  2. Output:
    • Should the output be the specific edge that when removed keeps the graph as a tree?
      • Yes, output the redundant edge.
  3. Edge Cases:
    • Should we handle cases with the minimum input size, i.e., edges contain only three nodes and two edges?
      • Yes, the function needs to handle the minimal case gracefully.

Strategy

To find the redundant connection, we use the Union-Find (Disjoint Set Union, DSU) data structure. This structure helps to efficiently manage and trace the connected components of the graph.

The approach involves:

  1. Union-Find Initialization:
    • Creating a parent array to keep track of the representative (or parent) of each node.
    • Creating a rank array to keep the tree flat by attaching smaller trees under larger trees.
  2. Processing each edge:
    • For each edge (u, v), check if u and v are already in the same connected component using find.
    • If they are in the same component (introduces a cycle), return the edge.
    • Otherwise, union the sets containing u and v.
  3. Union and Find Functions:
    • find(x): Recursively find the parent of x and perform path compression.
    • union(x, y): Attach trees representing x and y by size/rank.

By using Union-Find, we efficiently manage the connectivity information and detect the redundant edge.

Time Complexity

The time complexity of this approach is nearly O(n), due to the almost constant time operations provided by the Union-Find with path compression and union by rank. Specifically, it is O(α(n)) per operation, where α is the inverse Ackermann function, which grows very slowly.

Code

#include <vector>

using namespace std;

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<int> parent(n + 1);
        vector<int> rank(n + 1, 1);

        // Initialize parent array where each node is its own parent
        for (int i = 1; i <= n; ++i) {
            parent[i] = i;
        }

        for (const auto& edge : edges) {
            int u = edge[0], v = edge[1];
            if (find(parent, u) == find(parent, v)) {
                return {u, v};
            }
            unionSets(parent, rank, u, v);
        }

        // In a valid input according to problem statement, this line should never be reached.
        return {};
    }

private:
    int find(vector<int>& parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);  // Path compression
        }
        return parent[x];
    }

    void unionSets(vector<int>& parent, vector<int>& rank, int x, int y) {
        int rootX = find(parent, x);
        int rootY = find(parent, y);

        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
};

This code uses the Union-Find data structure to efficiently detect and return the redundant edge that introduces a cycle in the given graph.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI