Redundant Connection
Statement
Let there be an undirected graph consisting of n nodes. The graph is represented as a list called edges of length n, where edges[i] = [a, b] indicates there’s an edge between nodes a and b in the graph.
Return an edge that can be removed to make the graph a tree of n nodes. If there are multiple candidates for removal, return the edge that occurs last in edges.
Constraints
- 3 ≤
n≤ 100 edges.length()=nedges[i].length()= 2- 1 ≤
a<b≤n a≠b- There are no repeated edges
- The given graph is connected
- The graph contains only one cycle
Solution
"""
production algorithm
"""
class Solution:
def redundant_connection(self, edges):
"""
time complexity O(n)
space complexity O(n)
"""
size = float("-inf")
for u, v in edges:
size = max(size, u, v)
unionfind = UnionFind(size)
result = []
for u, v in edges:
if unionfind.connected(u, v):
result = [u, v]
unionfind.union(u, v)
return result
class UnionFind:
def __init__(self, size):
self.parent = [n for n in range(size + 1)]
self.size = [1 for _ in range(size + 1)]
def find(self, x):
"""
time complexity O(⍺(n))
space complexity O(n)
"""
if not self.parent[x] == x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""
time complexity O(⍺(n))
space complexity O(n)
"""
rootx = self.find(x)
rooty = self.find(y)
if not rootx == rooty:
if self.size[rootx] < self.size[rooty]:
rooty, rootx = rootx, rooty
self.parent[rooty] = rootx
self.size[rootx] += self.size[rooty]
def connected(self, x, y):
"""
time complexity O(⍺(n))
space complexity O(n)
"""
return self.find(x) == self.find(y)"""
unit tests
"""
from unittest import TestCase
from algorithms.union_find.redundant_connection.solution import Solution
class SolutionTestCase(TestCase):
def test_all_paths_cyclic(self):
# Given
edges = [(0, 1), (1, 2), (2, 3), (3, 4),
(4, 5), (5, 6), (6, 7), (7, 0)]
solution = Solution()
# When
actual = solution.redundant_connection(edges)
# Then
expected = [7, 0]
self.assertEqual(actual, expected)
def test_some_paths_cyclic(self):
# Given
edges = [(1, 2), (1, 3), (2, 4), (2, 5),
(3, 6), (3, 7), (4, 8), (7, 8)]
solution = Solution()
# When
actual = solution.redundant_connection(edges)
# Then
expected = [7, 8]
self.assertEqual(actual, expected)Strategy
Union Find.
Explanation
The algorithm uses a UnionFind data structure to find the last edge that should be removed in order to make the graph a tree. In other words, it finds the last edge in the graph that creates a cycle. First, it iterates the edges in order to find the largest vertex, that also indicates the size of the UnionFind data structure.
Next, the edges are iterated again. If two vertexes are connected in the UnionFind data structure, then the edge that connects them creates a cycle in the graph. Record the edge every time such a connection is found, and the last edge that creates a cycle in the graph will be found. In the last step of each iteration, union the vertexes so that cycles in the graph can be found.
The result, is that the last edge that creates a cycle in the graph will be found. Return the edge since it should be removed to make the graph a tree.
Time Complexity
The operations of a UnionFind data structure run in amortized time complexity O(⍺(n)), where ⍺(n) is the inverse Ackerman function that grows very slowly and returns constant output for all practical input with size n. Therefore, the time complexity of the algorithm depends on the number of edges. Let n be the number of edges. Then, the time complexity of the algorithm is O(n × ⍺(n)), or simply O(n).
Space Complexity
The UnionFind data structure uses auxiliary space with size n. Therefore, the auxiliary space complexity of the algorithm is O(n).
