Problem

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Examples

Example 1:

graph LR
	1 --- 2
	1 --- 3
	2 --- 3
  
1
2

Input: edges =[[1,2],[1,3],[2,3]]
Output: [2,3]

Example 2:

graph LR
	1 --> 2 & 4 & 5
	2 --> 3
	3 --> 4
  
1
2

Input: edges =[[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]

Solution

Method 1 - Union Find

We can iterate through edges and find both vertices of the edge to see if they belong to the same segment. If so, we’ve located our redundant edge and can return it. If not, we should merge the two different segments with union.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        UnionFind uf = new UnionFind(n);
        for (int[] edge: edges) {
            int u = edge[0];
            int v = edge[1];
            if (!uf.union(u - 1, v - 1)) {
                return new int[] {u, v};
            }
        }
        return new int[]{};
    }

    static class UnionFind {

		private int[] parent;

		private int[] rank;

		private int numComponents;

		public UnionFind(int n) {
			this.numComponents = n;
			makeSet();
		}

		private void makeSet() {
			rank = new int[numComponents];
			parent = new int[numComponents];

			for (int i = 0; i < parent.length; i++) {
				parent[i] = i;
				rank[i] = 0;
			}
		}

		public boolean union(int x, int y) {
			int root1 = find(x);
			int root2 = find(y);

			if (root1 == root2) {
				return false;
			}

			if (rank[root1] > rank[root2]) {
				parent[root2] = root1;
			} else {
				parent[root1] = root2;
			}

			if (rank[root1] == rank[root2]) {
				rank[root2] += 1;
			}

			numComponents--;
            return true;
		}

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

			return x;
		}

		public int getNumComponents() {
			return numComponents;
		}

        public boolean isFullyConnected() {
            return numComponents == 1;
        }
	}
}

Complexity

  • ⏰ Time complexity: O(n * α(n)), where N is number of vertices in the graph
    • Explanation: Using both path compression and union by size ensures that the amortized time per UnionFind operation is only α(n), which is optimal, where α(n) is the inverse Ackermann function. This function has a value α(n) < 5 for any value of n that can be written in this physical universe, so the disjoint-set operations take place in essentially constant time. Reference: https://en.wikipedia.org/wiki/Disjoint-set_data_structure
  • 🧺 Space complexity: O(n) as we store parent and rank arrays of size n in Union-Find data structure.

Method 2 - Using Bridges and Articulation Points

Although it’s less well-known than Union Find and DFS, this problem can be effectively addressed using Tarjan’s Bridge finding algorithm. By capturing the low and disc values for each node during traversal, we can identify any bridges.

In this problem, our goal is to find the last edge that is not a bridge. I incorporated a somewhat awkward swap logic since the bridge check is conducted post-traversal, but overall, this remains a standard implementation of the Bridge finding algorithm.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

class Solution {
    
    int time = 1;
    public int[] findRedundantConnection(int[][] edges) {

        int n = edges.length;
        int[] low = new int[n + 1];
        int[] disc = new int[n + 1];
        
        List<List<Integer>> adjList = buildGraph(edges);
        dfs(adjList, 1, low, disc, -1);
        
        for (int i = n - 1; i >= 0; i--) {
            int[] edge = edges[i];
            int u = edge[0];
            int v = edge[1];
            
            // Swap since u must always be the earlier node during our check
            if (disc[u] > disc[v]) {
                int temp = u;
                u = v;
                v = temp;
            }
            
            if (low[v] > disc[u]){
                // We have bridge
                continue;
            } else {
                return edge;
            }
        }
        
        return null;
    }
    
    private List<List<Integer>> buildGraph(int[][] edges) {
        int n = edges.length;
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adjList.add(new ArrayList<>());
        }
        
        for (int[] edge: edges) {
            int src = edge[0];
            int dst = edge[1];
            adjList.get(src).add(dst);
            adjList.get(dst).add(src);
        }
        
        return adjList;
    }
    
    private void dfs(List<List<Integer>> adjList, int u, int[] low, int[] disc, int parent) {
        if (disc[u] != 0) {
            return;
        }
        
        disc[u] = time;
        low[u] = time;
        time++;
        
        for (int v: adjList.get(u)) {
            if (v == parent) {
                continue;
            }
            if (disc[v] == 0) {
                dfs(adjList, v, low, disc, u);
                low[u] = Math.min(low[u], low[v]);
            } else {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }
}