I'm trying to solve problem 1319 on Leetcode, which is as follows:
There are n computers numbered from 0 to n - 1 connected by ethernet cables connections forming a network where connections[i] = [ai, bi] represents a connection between computers ai and bi. Any computer can reach any other computer directly or indirectly through the network.
You are given an initial computer network connections. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected.
Return the minimum number of times you need to do this in order to make all the computers connected. If it is not possible, return -1.
Thinking on this a little, I came up with the following non-working approach and associated code:
First, convert the edge list into an adjacency list of connections. Go to the first computer and see how many computers are accessible from that one (using e.g DFS). Additionally, keep track of the number of connections that repeatedly try to access a visited node, indicating that there's a wire we can get rid of. This represents a connected component. Find the next non-visited node and repeat the same process. At the end, determine if the number of wires we counted is >= the number of connected components - 1
from typing import DefaultDict, List, Set
from collections import defaultdict
class Solution:
def makeConnected(self, n: int, connections: List[List[int]]) -> int:
def dfs(
adj_list: DefaultDict[int, List[int]], computer: int, visited: Set[int]
) -> int:
"""Returns the number of removable wires from this connected component"""
num_removable_wires = 0
stack = [computer]
while len(stack) > 0:
current = stack.pop()
# Already been here, so can remove this wire
if current in visited:
num_removable_wires += 1
continue
visited.add(current)
if current in adj_list:
for neighbor in adj_list[current]:
stack.append(neighbor)
return num_removable_wires
adj_list = defaultdict(list)
for connection in connections:
adj_list[connection[0]].append(connection[1])
# adj_list[connection[1]].append(connection[0])
total_removable_wires = 0
num_components = 0
visited = set()
for computer in adj_list.keys():
if computer in visited:
continue
num_components += 1
total_removable_wires += dfs(adj_list, computer, visited)
# Add computers that are completely isolated
num_components += n - len(visited)
return (
num_components - 1
if total_removable_wires >= num_components - 1
else -1
)
if __name__ == "__main__":
print(Solution().makeConnected(6, [[0, 1], [0, 2], [0, 3], [1, 2]]))
print(
Solution().makeConnected(
11,
[
[1, 4],
[0, 3],
[1, 3],
[3, 7],
[2, 7],
[0, 1],
[2, 4],
[3, 6],
[5, 6],
[6, 7],
[4, 7],
[0, 7],
[5, 7],
],
)
)
For the first test case, this code works as expected. For the second, I realized that for certain vertices, e.g 1, the only vertices accessible, directly or indirectly, are 4, 3, 7, and 6 since the edges are only placed in one direction in the adjacency list. The code then incorrectly determines that vertex 0 is part of a new component. To fix this, I tried to adjust the following, uncommenting the second line of code when constructing the adjacency list, to add both sides of the same edge:
for connection in connections:
adj_list[connection[0]].append(connection[1])
adj_list[connection[1]].append(connection[0])
However, while this fixes the second test case, this now breaks the first. Now, when the code reaches e.g 3 from 0 and sees that 0 is a neighbor already visited, it incorrectly states that edge is redundant even though it was just traversed on the way to 3.
How can I correctly count the number of redundant edges (or removable wires) in the context of this problem? Note that I realize there are better approaches in the Leetcode solutions tab that I could implement, but I was wondering what I am doing wrong for my solution attempt and whether it is possible to correct this existing approach.
When you do:
adj_list = defaultdict(list)
for connection in connections:
adj_list[connection[0]].append(connection[1])
# adj_list[connection[1]].append(connection[0])
You will only create dictionary keys for one-directional edges.
You need to add the edges in the reverse direction (that you have commented out) and then, when you are performing the DFS, you need to count half-edges (and adjust for the tree edges that are not removable):
from typing import DefaultDict, List, Set
from collections import defaultdict
def dfs(
adj_list: DefaultDict[int, List[int]],
computer: int,
visited: Set[int]
) -> int:
"""Returns the number of removable wires from this connected component"""
stack = [computer]
# The root vertex of the DFS is only visited once so add an extra
# half-edge to adjust.
removable_half_edges = 1
while len(stack) > 0:
current = stack.pop()
# count each half-edge as it is visited.
removable_half_edges += 1
if current not in visited:
# Tree edges are not removable so do not count both half-edges.
removable_half_edges -= 2
visited.add(current)
stack.extend(adj_list[current])
# return the number of bi-directional edges
return removable_half_edges // 2
class Solution:
def makeConnected(self, n: int, connections: List[List[int]]) -> int:
adj_list = defaultdict(list)
for connection in connections:
adj_list[connection[0]].append(connection[1])
adj_list[connection[1]].append(connection[0])
total_removable_wires = 0
num_components = 0
visited = set()
for computer in adj_list.keys():
if computer in visited:
continue
num_components += 1
total_removable_wires += dfs(adj_list, computer, visited)
# Add computers that are completely isolated
num_components += n - len(visited)
return (
num_components - 1
if total_removable_wires >= num_components - 1
else -1
)
if __name__ == "__main__":
tests = (
(4, [[0,1],[0,2],[1,2]], 1),
(6, [[0,1],[0,2],[0,3],[1,2],[1,3]], 2),
(10, [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]], 5),
(10, [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4]], 5),
(10, [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3]], -1),
(6, [[0,1],[0,2],[0,3],[1,2]], -1),
(11, [[1, 4], [0, 3], [1, 3], [3, 7], [2, 7], [0, 1], [2, 4], [3, 6], [5, 6], [6, 7], [4, 7], [0, 7], [5, 7]], 3),
)
solution = Solution()
for n, connections, expected in tests:
output = solution.makeConnected(n, connections)
if output == expected:
print("PASS")
else:
print(f"FAIL: {n}, {connections} -> {output} expected {expected}.")
You could also simplify the data-structures by creating a Computer class to store whether the computer has been visited and the adjacency list and then iterating over those to find the connected components:
from __future__ import annotations
class Computer:
connections: list[Computer]
dfs_visited: bool
def __init__(self) -> None:
self.connections = []
self.dfs_visited = False
class Solution:
def makeConnected(
self,
n: int,
connections: list[list[int]],
) -> int:
if len(connections) < n - 1:
return -1
removable_cables: int = 0
connected_networks: int = 0
computers = [Computer() for _ in range(n)]
for f, t in connections:
computers[f].connections.append(computers[t])
computers[t].connections.append(computers[f])
for computer in computers:
if computer.dfs_visited:
continue
connected_networks += 1
removable_half_edges = 1
stack: list[Computer] = [computer]
while stack:
comp = stack.pop()
removable_half_edges += 1
if not comp.dfs_visited:
removable_half_edges -= 2
comp.dfs_visited = True
stack.extend(comp.connections)
removable_cables += removable_half_edges / 2
return (
(connected_networks - 1)
if removable_cables >= (connected_networks - 1)
else -1
)
if __name__ == "__main__":
tests = (
(4, [[0,1],[0,2],[1,2]], 1),
(6, [[0,1],[0,2],[0,3],[1,2],[1,3]], 2),
(10, [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]], 5),
(10, [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4]], 5),
(10, [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3]], -1),
(6, [[0,1],[0,2],[0,3],[1,2]], -1),
(11, [[1, 4], [0, 3], [1, 3], [3, 7], [2, 7], [0, 1], [2, 4], [3, 6], [5, 6], [6, 7], [4, 7], [0, 7], [5, 7]], 3),
)
solution = Solution()
for n, connections, expected in tests:
output = solution.makeConnected(n, connections)
if output == expected:
print("PASS")
else:
print(f"FAIL: {n}, {connections} -> {output} expected {expected}.")