Redundant Connection (Find Cycle Edge)

🎯

Redundant Connection (Find Cycle Edge)

mediumGRAPHAmazonGoogleFacebook

Imagine you are managing a network of computers connected by cables. You want to add cables without creating loops that cause network issues. How do you detect the first cable that creates a cycle?

💡 This problem is about detecting the first edge that creates a cycle in an undirected graph. Beginners often struggle because cycle detection can be done in multiple ways, and understanding why union-find is efficient requires grasping the concept of connected components and sets.

📋

Problem Statement

Given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added, find the edge that, when added, creates a cycle. The input is a list of edges where each edge connects two nodes. Return the edge that can be removed so that the resulting graph is a tree of n nodes.

1 ≤ n ≤ 10^5edges.length == nedges[i].length == 21 ≤ edges[i][0] < edges[i][1] ≤ nNo repeated edgesThe graph is connected and has exactly one cycle

💡

Example

Input"[[1,2],[1,3],[2,3]]"

Output[2,3]

Edges [1,2] and [1,3] form a tree. Adding [2,3] creates a cycle, so [2,3] is the redundant connection.

• Minimum nodes (n=2) with one edge → output that edge
• Cycle formed by last edge in input → output last edge
• Cycle formed by an early edge → output that edge
• Edges forming a chain with a cycle at the end → output cycle edge

⚠️

Common Mistakes

Not checking if nodes are already connected before union

Incorrectly merges sets and misses cycle detection

✅ Always check if find(u) == find(v) before union

Forgetting path compression in find

Union-find operations become slower, risking TLE on large inputs

✅ Implement path compression by setting parent[x] = find(parent[x])

Not initializing parent array correctly (e.g., zero-based vs one-based indexing)

Index errors or wrong parents leading to incorrect results

✅ Initialize parent array with parent[i] = i for all nodes

Using DFS brute force approach without pruning

Solution times out on large inputs

✅ Switch to union-find for efficient cycle detection

Union by rank not implemented, causing skewed trees

Find operations degrade to O(n) in worst case

✅ Implement union by rank to keep trees balanced

🧠

Brute Force (Cycle Detection by DFS for Each Edge)

💡 This approach exists to build intuition on cycle detection by explicitly checking connectivity before adding each edge. It is slow but conceptually straightforward.

Intuition

For each edge, remove it temporarily and check if the graph remains connected without cycles. If yes, that edge is redundant. This involves checking connectivity repeatedly.

Algorithm

1. Initialize an empty graph with n nodes and no edges.
2. For each edge in edges:
3. Use DFS to check if the two nodes of the edge are already connected in the current graph.
4. If connected, return this edge as the redundant connection.
5. Otherwise, add the edge to the graph and continue.

💡 The main difficulty is understanding how to check connectivity efficiently and why checking before adding an edge detects cycles.

</>

Code

from collections import defaultdict

def findRedundantConnection(edges):
    graph = defaultdict(list)

    def dfs(source, target, visited):
        if source == target:
            return True
        visited.add(source)
        for neighbor in graph[source]:
            if neighbor not in visited:
                if dfs(neighbor, target, visited):
                    return True
        return False

    for u, v in edges:
        visited = set()
        if u in graph and v in graph and dfs(u, v, visited):
            return [u, v]
        graph[u].append(v)
        graph[v].append(u)

# Driver code
if __name__ == '__main__':
    edges = [[1,2],[1,3],[2,3]]
    print(findRedundantConnection(edges))  # Output: [2,3]

Line Notes

graph = defaultdict(list)Initialize adjacency list to represent the graph so we can efficiently track neighbors.

def dfs(source, target, visited):Define DFS to check if target node is reachable from source node, indicating connectivity.

if source == target:Base case: if current node is target, connectivity is confirmed.

visited.add(source)Mark current node as visited to avoid cycles and repeated work.

for neighbor in graph[source]:Explore all neighbors of the current node to continue DFS traversal.

if neighbor not in visited:Only visit neighbors not yet visited to prevent infinite loops.

if dfs(neighbor, target, visited):If any neighbor leads to target, propagate True upwards.

if u in graph and v in graph and dfs(u, v, visited):Check if u and v are already connected before adding the edge, indicating a cycle.

graph[u].append(v)Add edge from u to v to the graph as it does not create a cycle.

graph[v].append(u)Add edge from v to u to maintain undirected graph representation.

import java.util.*;

public class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();

        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            Set<Integer> visited = new HashSet<>();
            if (graph.containsKey(u) && graph.containsKey(v) && dfs(u, v, graph, visited)) {
                return edge;
            }
            graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
            graph.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
        }
        return new int[0];
    }

    private boolean dfs(int source, int target, Map<Integer, List<Integer>> graph, Set<Integer> visited) {
        if (source == target) return true;
        visited.add(source);
        if (!graph.containsKey(source)) return false;
        for (int neighbor : graph.get(source)) {
            if (!visited.contains(neighbor)) {
                if (dfs(neighbor, target, graph, visited)) return true;
            }
        }
        return false;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] edges = {{1,2},{1,3},{2,3}};
        int[] res = sol.findRedundantConnection(edges);
        System.out.println(Arrays.toString(res)); // Output: [2,3]
    }
}

Line Notes

Map<Integer, List<Integer>> graph = new HashMap<>();Initialize adjacency list to represent the graph for efficient neighbor lookups.

if (graph.containsKey(u) && graph.containsKey(v) && dfs(u, v, graph, visited)) {Check if u and v are already connected, indicating adding this edge creates a cycle.

graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);Add edge from u to v to the graph as it does not create a cycle.

graph.computeIfAbsent(v, k -> new ArrayList<>()).add(u);Add edge from v to u to maintain undirected graph representation.

if (source == target) return true;Base case for DFS: found the target node, confirming connectivity.

visited.add(source);Mark current node as visited to avoid revisiting and infinite loops.

if (!graph.containsKey(source)) return false;If no neighbors, cannot reach target from here.

for (int neighbor : graph.get(source)) {Explore all neighbors of current node in DFS.

if (!visited.contains(neighbor)) {Visit only unvisited neighbors to prevent cycles.

if (dfs(neighbor, target, graph, visited)) return true;If any neighbor leads to target, propagate True.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;

class Solution {
public:
    bool dfs(int source, int target, unordered_map<int, vector<int>>& graph, unordered_set<int>& visited) {
        if (source == target) return true;
        visited.insert(source);
        if (graph.find(source) == graph.end()) return false;
        for (int neighbor : graph[source]) {
            if (visited.find(neighbor) == visited.end()) {
                if (dfs(neighbor, target, graph, visited)) return true;
            }
        }
        return false;
    }

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        unordered_map<int, vector<int>> graph;
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            unordered_set<int> visited;
            if (graph.count(u) && graph.count(v) && dfs(u, v, graph, visited)) {
                return edge;
            }
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        return {};
    }
};

int main() {
    Solution sol;
    vector<vector<int>> edges = {{1,2},{1,3},{2,3}};
    vector<int> res = sol.findRedundantConnection(edges);
    cout << "[" << res[0] << "," << res[1] << "]" << endl; // Output: [2,3]
    return 0;
}

Line Notes

unordered_map<int, vector<int>> graph;Adjacency list to represent the graph for efficient neighbor access.

if (graph.count(u) && graph.count(v) && dfs(u, v, graph, visited)) {Check if u and v are already connected, indicating a cycle if edge added.

graph[u].push_back(v);Add edge from u to v as it does not create a cycle.

graph[v].push_back(u);Add edge from v to u to maintain undirected graph.

if (source == target) return true;DFS base case: found target node confirming connectivity.

visited.insert(source);Mark current node as visited to avoid revisiting.

if (graph.find(source) == graph.end()) return false;If no neighbors, cannot reach target from here.

for (int neighbor : graph[source]) {Explore neighbors of current node in DFS.

if (visited.find(neighbor) == visited.end()) {Visit only unvisited neighbors to prevent cycles.

if (dfs(neighbor, target, graph, visited)) return true;If neighbor leads to target, propagate True.

function findRedundantConnection(edges) {
    const graph = new Map();

    function dfs(source, target, visited) {
        if (source === target) return true;
        visited.add(source);
        if (!graph.has(source)) return false;
        for (const neighbor of graph.get(source)) {
            if (!visited.has(neighbor)) {
                if (dfs(neighbor, target, visited)) return true;
            }
        }
        return false;
    }

    for (const [u, v] of edges) {
        const visited = new Set();
        if (graph.has(u) && graph.has(v) && dfs(u, v, visited)) {
            return [u, v];
        }
        if (!graph.has(u)) graph.set(u, []);
        if (!graph.has(v)) graph.set(v, []);
        graph.get(u).push(v);
        graph.get(v).push(u);
    }
}

// Test
console.log(findRedundantConnection([[1,2],[1,3],[2,3]])); // Output: [2,3]

Line Notes

const graph = new Map();Initialize adjacency list as a Map for efficient neighbor lookups.

function dfs(source, target, visited) {DFS helper to check if target is reachable from source.

if (source === target) return true;Base case: found target node confirming connectivity.

visited.add(source);Mark current node as visited to avoid revisiting.

if (!graph.has(source)) return false;If no neighbors, cannot reach target from here.

for (const neighbor of graph.get(source)) {Explore neighbors of current node in DFS.

if (!visited.has(neighbor)) {Visit only unvisited neighbors to prevent cycles.

if (dfs(neighbor, target, visited)) return true;If neighbor leads to target, propagate True.

if (graph.has(u) && graph.has(v) && dfs(u, v, visited)) {Check if u and v are already connected before adding edge.

graph.get(u).push(v);Add edge from u to v as it does not create a cycle.

graph.get(v).push(u);Add edge from v to u to maintain undirected graph.

⏱

Complexity

TimeO(n^2)

SpaceO(n)

For each edge, DFS can take O(n) in worst case, repeated for n edges → O(n^2). Space is O(n) for graph and visited set.

💡 For n=1000, this means up to 1,000,000 operations, which is slow for large inputs.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but helps understand cycle detection and connectivity checks.

🧠

Union-Find (Disjoint Set Union) - Basic Implementation

💡 Union-Find is a classic data structure to efficiently detect cycles by tracking connected components. This approach introduces union-find basics without optimizations.

Intuition

If two nodes of an edge belong to the same connected component, adding this edge creates a cycle. Otherwise, union their sets.

Algorithm

1. Initialize parent array where each node is its own parent.
2. For each edge (u, v):
3. Find the root parent of u and v.
4. If roots are the same, return this edge as redundant.
5. Otherwise, union the sets by updating parent.

💡 Understanding how find and union work is key to grasping why this detects cycles efficiently.

</>

Code

def findRedundantConnection(edges):
    n = len(edges)
    parent = list(range(n+1))

    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x

    def union(a, b):
        rootA = find(a)
        rootB = find(b)
        if rootA == rootB:
            return False
        parent[rootB] = rootA
        return True

    for u, v in edges:
        if not union(u, v):
            return [u, v]

# Driver code
if __name__ == '__main__':
    edges = [[1,2],[1,3],[2,3]]
    print(findRedundantConnection(edges))  # Output: [2,3]

Line Notes

parent = list(range(n+1))Initialize each node as its own parent to represent separate sets initially.

def find(x):Find the root parent of node x to identify its set.

while parent[x] != x:Traverse up the parent chain until the root is found.

def union(a, b):Union two sets if their root parents differ.

if rootA == rootB:If roots are the same, adding edge creates a cycle.

parent[rootB] = rootAMerge sets by making rootA the parent of rootB.

public class Solution {
    int[] parent;

    public int find(int x) {
        while (parent[x] != x) {
            x = parent[x];
        }
        return x;
    }

    public boolean union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA == rootB) return false;
        parent[rootB] = rootA;
        return true;
    }

    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        parent = new int[n+1];
        for (int i = 1; i <= n; i++) parent[i] = i;

        for (int[] edge : edges) {
            if (!union(edge[0], edge[1])) return edge;
        }
        return new int[0];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] edges = {{1,2},{1,3},{2,3}};
        int[] res = sol.findRedundantConnection(edges);
        System.out.println(java.util.Arrays.toString(res)); // Output: [2,3]
    }
}

Line Notes

parent = new int[n+1];Initialize parent array to represent each node as its own set.

while (parent[x] != x) {Find root parent by climbing parent links.

if (rootA == rootB) return false;Detect cycle if both nodes share the same root.

parent[rootB] = rootA;Union sets by linking rootB to rootA.

for (int i = 1; i <= n; i++) parent[i] = i;Set each node as its own parent initially.

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> parent;

    int find(int x) {
        while (parent[x] != x) {
            x = parent[x];
        }
        return x;
    }

    bool unionSet(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA == rootB) return false;
        parent[rootB] = rootA;
        return true;
    }

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        parent.resize(n+1);
        for (int i = 1; i <= n; i++) parent[i] = i;

        for (auto& edge : edges) {
            if (!unionSet(edge[0], edge[1])) return edge;
        }
        return {};
    }
};

int main() {
    Solution sol;
    vector<vector<int>> edges = {{1,2},{1,3},{2,3}};
    vector<int> res = sol.findRedundantConnection(edges);
    cout << "[" << res[0] << "," << res[1] << "]" << endl; // Output: [2,3]
    return 0;
}

Line Notes

parent.resize(n+1);Initialize parent vector size to represent each node as its own set.

while (parent[x] != x) {Find root parent by climbing parent links.

if (rootA == rootB) return false;Detect cycle if both nodes share the same root.

parent[rootB] = rootA;Union sets by linking rootB to rootA.

for (int i = 1; i <= n; i++) parent[i] = i;Set each node as its own parent initially.

function findRedundantConnection(edges) {
    const n = edges.length;
    const parent = Array(n+1).fill(0).map((_, i) => i);

    function find(x) {
        while (parent[x] !== x) {
            x = parent[x];
        }
        return x;
    }

    function union(a, b) {
        const rootA = find(a);
        const rootB = find(b);
        if (rootA === rootB) return false;
        parent[rootB] = rootA;
        return true;
    }

    for (const [u, v] of edges) {
        if (!union(u, v)) return [u, v];
    }
}

// Test
console.log(findRedundantConnection([[1,2],[1,3],[2,3]])); // Output: [2,3]

Line Notes

const parent = Array(n+1).fill(0).map((_, i) => i);Initialize parent array with each node as its own parent.

while (parent[x] !== x) {Find root parent by climbing parent links.

if (rootA === rootB) return false;Detect cycle if both nodes share the same root.

parent[rootB] = rootA;Union sets by linking rootB to rootA.

for (const [u, v] of edges) {Process each edge to detect cycle.

⏱

Complexity

TimeO(n * α(n))

SpaceO(n)

Each union/find operation is almost O(1) amortized due to inverse Ackermann function α(n). For n edges, total O(n * α(n)) ~ O(n).

💡 For n=100000, this means roughly 100000 operations, which is efficient for large inputs.

Interview Verdict: Accepted

This approach is efficient and accepted in interviews, but can be improved with path compression.

🧠

Union-Find with Path Compression and Union by Rank

💡 This is the optimal union-find implementation that improves find and union operations by flattening trees and balancing unions, making it very efficient.

Intuition

Path compression flattens the tree during find operations, and union by rank attaches smaller trees under larger ones to keep trees shallow, speeding up future operations.

Algorithm

1. Initialize parent and rank arrays; each node is its own parent with rank 0.
2. For each edge (u, v):
3. Find root parents of u and v with path compression.
4. If roots are same, return edge as redundant.
5. Otherwise, union by attaching lower rank tree under higher rank tree and update ranks.

💡 Understanding path compression and rank is key to grasping why this approach is optimal.

</>

Code

def findRedundantConnection(edges):
    n = len(edges)
    parent = list(range(n+1))
    rank = [0]*(n+1)

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])  # Path compression
        return parent[x]

    def union(a, b):
        rootA = find(a)
        rootB = find(b)
        if rootA == rootB:
            return False
        if rank[rootA] < rank[rootB]:
            parent[rootA] = rootB
        elif rank[rootB] < rank[rootA]:
            parent[rootB] = rootA
        else:
            parent[rootB] = rootA
            rank[rootA] += 1
        return True

    for u, v in edges:
        if not union(u, v):
            return [u, v]

# Driver code
if __name__ == '__main__':
    edges = [[1,2],[1,3],[2,3]]
    print(findRedundantConnection(edges))  # Output: [2,3]

Line Notes

rank = [0]*(n+1)Initialize rank array to track tree height for balancing unions.

if parent[x] != x:If x is not root, recurse to find root with path compression.

parent[x] = find(parent[x])Path compression flattens tree to speed up future finds.

if rank[rootA] < rank[rootB]:Attach smaller rank tree under larger to keep tree shallow.

elif rank[rootB] < rank[rootA]:Attach smaller rank tree under larger.

else:If ranks equal, attach one under other and increment rank.

rank[rootA] += 1Increment rank when two trees of equal rank are merged.

public class Solution {
    int[] parent, rank;

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }

    public boolean union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA == rootB) return false;
        if (rank[rootA] < rank[rootB]) {
            parent[rootA] = rootB;
        } else if (rank[rootB] < rank[rootA]) {
            parent[rootB] = rootA;
        } else {
            parent[rootB] = rootA;
            rank[rootA]++;
        }
        return true;
    }

    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        parent = new int[n+1];
        rank = new int[n+1];
        for (int i = 1; i <= n; i++) parent[i] = i;

        for (int[] edge : edges) {
            if (!union(edge[0], edge[1])) return edge;
        }
        return new int[0];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] edges = {{1,2},{1,3},{2,3}};
        int[] res = sol.findRedundantConnection(edges);
        System.out.println(java.util.Arrays.toString(res)); // Output: [2,3]
    }
}

Line Notes

rank = new int[n+1];Initialize rank array to track tree heights for balancing.

if (parent[x] != x) {Path compression during find to flatten tree.

parent[x] = find(parent[x]);Flatten tree for faster future finds.

if (rank[rootA] < rank[rootB]) {Attach smaller rank tree under larger.

else if (rank[rootB] < rank[rootA]) {Attach smaller rank tree under larger.

else {If ranks equal, attach and increment rank.

rank[rootA]++;Increment rank when merging equal rank trees.

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> parent, rank;

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }

    bool unionSet(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA == rootB) return false;
        if (rank[rootA] < rank[rootB]) {
            parent[rootA] = rootB;
        } else if (rank[rootB] < rank[rootA]) {
            parent[rootB] = rootA;
        } else {
            parent[rootB] = rootA;
            rank[rootA]++;
        }
        return true;
    }

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        parent.resize(n+1);
        rank.resize(n+1, 0);
        for (int i = 1; i <= n; i++) parent[i] = i;

        for (auto& edge : edges) {
            if (!unionSet(edge[0], edge[1])) return edge;
        }
        return {};
    }
};

int main() {
    Solution sol;
    vector<vector<int>> edges = {{1,2},{1,3},{2,3}};
    vector<int> res = sol.findRedundantConnection(edges);
    cout << "[" << res[0] << "," << res[1] << "]" << endl; // Output: [2,3]
    return 0;
}

Line Notes

rank.resize(n+1, 0);Initialize rank vector with zeros to track tree heights.

if (parent[x] != x) {Path compression in find to flatten tree.

parent[x] = find(parent[x]);Flatten tree for efficiency in future finds.

if (rank[rootA] < rank[rootB]) {Attach smaller tree under bigger to keep tree shallow.

else if (rank[rootB] < rank[rootA]) {Attach smaller tree under bigger.

else {If ranks equal, attach and increment rank.

rank[rootA]++;Increase rank when merging equal rank trees.

function findRedundantConnection(edges) {
    const n = edges.length;
    const parent = Array(n+1).fill(0).map((_, i) => i);
    const rank = Array(n+1).fill(0);

    function find(x) {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }

    function union(a, b) {
        const rootA = find(a);
        const rootB = find(b);
        if (rootA === rootB) return false;
        if (rank[rootA] < rank[rootB]) {
            parent[rootA] = rootB;
        } else if (rank[rootB] < rank[rootA]) {
            parent[rootB] = rootA;
        } else {
            parent[rootB] = rootA;
            rank[rootA]++;
        }
        return true;
    }

    for (const [u, v] of edges) {
        if (!union(u, v)) return [u, v];
    }
}

// Test
console.log(findRedundantConnection([[1,2],[1,3],[2,3]])); // Output: [2,3]

Line Notes

const rank = Array(n+1).fill(0);Initialize rank array to track tree height for balancing.

if (parent[x] !== x) {Path compression during find to flatten tree.

parent[x] = find(parent[x]);Flatten tree for faster future finds.

if (rank[rootA] < rank[rootB]) {Attach smaller rank tree under larger.

else if (rank[rootB] < rank[rootA]) {Attach smaller rank tree under larger.

else {If ranks equal, attach and increment rank.

rank[rootA]++;Increment rank when merging equal rank trees.

⏱

Complexity

TimeO(n * α(n))

SpaceO(n)

Path compression and union by rank make each union/find operation almost O(1) amortized, so total O(n * α(n)) ~ O(n).

💡 This is the fastest practical approach for large inputs, making it ideal for interviews.

Interview Verdict: Accepted / Optimal

This is the recommended approach to implement in interviews for efficiency and clarity.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the optimized union-find with path compression and union by rank in 95% of interviews for best performance and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (DFS connectivity check)	O(n^2)	O(n)	Yes (deep recursion in DFS)	N/A	Mention only - never code
2. Union-Find Basic	O(n * α(n))	O(n)	No	N/A	Good for initial implementation
3. Union-Find with Path Compression and Union by Rank	O(n * α(n))	O(n)	No	N/A	Optimal approach to implement

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and confirm input format.Step 2: Describe brute force approach to detect cycles by DFS connectivity checks.Step 3: Introduce union-find data structure and explain how it detects cycles efficiently.Step 4: Implement basic union-find and then optimize with path compression and union by rank.Step 5: Test code with sample inputs and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of cycle detection, graph connectivity, and efficient data structures like union-find.

Common Follow-ups

• What if the graph is directed? → Use DFS with recursion stack to detect cycles.
• How to find all redundant edges? → Modify union-find or use DFS to detect multiple cycles.

💡 These follow-ups test your ability to adapt cycle detection to different graph types and requirements.

🔍

Pattern Recognition

When to Use

1) Graph with edges possibly forming cycles, 2) Need to detect first cycle edge, 3) Undirected graph, 4) Efficient cycle detection required

Signature Phrases

redundant connectionfind the edge that creates a cycle

NOT This Pattern When

Cycle detection in directed graphs (requires DFS with recursion stack, not union-find)

Similar Problems

Detect Cycle in Undirected Graph - general cycle detectionNumber of Connected Components in an Undirected Graph - union-find usageGraph Valid Tree - check if graph is a tree using union-find

Practice

1. You are given a graph with edges of three types: edges usable by Alice only, edges usable by Bob only, and edges usable by both. The goal is to remove the maximum number of edges while ensuring both Alice and Bob can still traverse the entire graph. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. A greedy approach that processes type 3 edges first using union-find, then type 1 and 2 edges separately.

B. A brute force approach that tries all subsets of edges and checks connectivity for both Alice and Bob.

C. A dynamic programming approach that counts ways to connect nodes with subsets of edges.

D. A shortest path algorithm like Dijkstra's applied separately for Alice and Bob.

Solution

1. Step 1: Understand problem constraints

   The problem requires maximizing edge removals while keeping the graph fully traversable for both Alice and Bob, who share some edges (type 3) and have exclusive edges (type 1 and 2).

2. Step 2: Identify the best approach

   Processing type 3 edges first with union-find maximizes shared connectivity, then adding exclusive edges ensures full connectivity for both. This greedy union-find approach guarantees optimality, unlike brute force (too slow), DP (not applicable), or shortest path (irrelevant).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy union-find with type 3 edges first -> optimal [OK]

Hint: Process shared edges first to maximize connectivity [OK]

Common Mistakes:

• Trying brute force despite exponential complexity
• Ignoring type 3 edges first
• Using shortest path algorithms incorrectly

2. You are given a list of equations between variables, each either asserting equality (e.g., a==b) or inequality (e.g., a!=b). Which algorithmic approach best guarantees an efficient and correct solution to determine if all equations can be satisfied simultaneously?

easy

A. Union-Find data structure with two passes: first union all equalities, then check inequalities

B. Greedy approach that processes equations in input order, merging sets as it goes

C. Dynamic programming to track variable equivalences and contradictions

D. Brute force checking all pairs of variables for contradictions repeatedly

Solution

1. Step 1: Understand problem constraints

   The problem requires grouping variables into equivalence classes based on equalities and then verifying inequalities do not contradict these groups.

2. Step 2: Identify suitable algorithm

   Union-Find efficiently merges sets for equalities and then checks inequalities in a separate pass, ensuring correctness and near-linear time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Union-Find handles equivalence classes efficiently [OK]

Hint: Separate equality and inequality processing [OK]

Common Mistakes:

• Assuming greedy order works
• Using DP without clear state
• Brute force is too slow

3. Given the following code snippet implementing the union-find approach for Swim in Rising Water, and the input grid:

grid = [
  [0, 2],
  [1, 3]
]

# After sorting cells by elevation, what is the earliest time returned by swimInWater(grid)?

What is the returned value?

easy

A. 1

B. 2

C. 0

D. 3

Solution

1. Step 1: Sort cells by elevation

   Sorted cells: (0,0,0), (1,1,0), (2,0,1), (3,1,1)

2. Step 2: Union adjacent cells with elevation ≤ current

   At elevation=0, only (0,0) is active; no union with end. At elevation=1, union (1,0) with (0,0) possible. At elevation=2, union (0,1) with (0,0) or (1,0). At elevation=3, union (1,1) with neighbors, connecting start and end.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Earliest time when start and end connected is elevation 3 [OK]

Hint: Trace union-find merges in elevation order [OK]

Common Mistakes:

• Returning elevation before union-find connects start and end
• Confusing cell indices or union conditions
• Off-by-one errors in elevation comparisons

4. What is the time complexity of the optimal union-find approach with early contradiction detection for satisfiability of equality equations, assuming n equations and a fixed alphabet of 26 variables?

medium

A. O(n^2) due to repeated find operations without optimization

B. O(n α(n)) where α(n) is the inverse Ackermann function, nearly constant

C. O(n log n) because of union by rank and path compression overhead

D. O(n) since each equation is processed once with constant-time unions

Solution

1. Step 1: Identify union-find operations

   Each union or find operation runs in amortized O(α(n)) time due to path compression and union by rank.

2. Step 2: Count total operations

   Processing n equations involves at most 2n union/find calls, so total time is O(n α(n)).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Union-find nearly linear time complexity [OK]

Hint: Inverse Ackermann function is nearly constant [OK]

Common Mistakes:

• Confusing α(n) with log n
• Assuming O(n) without considering find complexity

5. Suppose you want to find a minimum spanning forest (MST for each connected component) in a graph that may be disconnected. Which modification to the Kruskal's algorithm with union-find is necessary to correctly handle this scenario?

hard

A. Remove the break condition and process all edges to connect all components separately

B. Use DFS to find connected components first, then run Kruskal on each separately

C. Stop after adding n-1 edges, as usual, since MST covers all nodes

D. Add edges only if they connect nodes in the same component to avoid cycles

Solution

1. Step 1: Understand MST vs MST forest

   In disconnected graphs, MST is a forest; stopping after n-1 edges assumes connectivity, which may not hold.

2. Step 2: Modify Kruskal to process all edges

   Removing the break condition allows union-find to connect all components separately, building MST forest.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Process all edges to cover disconnected components [OK]

Hint: Don't stop early if graph is disconnected; build MST forest instead [OK]

Common Mistakes:

• Stopping early assuming graph is connected
• Running DFS first adds unnecessary complexity
• Misusing union-find to connect nodes in same component