Find number of redundant edges in components of a graph

Question

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.

Answer 1

• There are several issues in your implementation. Most importantly, this is the key issue, and total_removable_wires are not being correctly calculated:

total_removable_wires += dfs(adj_list, computer, visited)

---

Algorithm

• We can simply handle the edge cases right at the beginning:

if len(connections) < n - 1: return -1

• We choose a simple data structure for visiting the nodes: visited = [0] * n.

• In our dfs, if the node is in the visited, we return 0, then we see the neighbors recursively, and finally we return 1.

• The sum of the dfs(node) minus one is simply the result.

Code

from typing import List


class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n - 1:
            return -1

        def dfs(node) -> int:
            if visited[node]:
                return 0

            visited[node] = 1
            for i in adj_list[node]:
                dfs(i)
            return 1

        adj_list = [set() for _ in range(n)]

        for i, j in connections:
            adj_list[i].add(j)
            adj_list[j].add(i)

        visited = [0] * n

        return sum(dfs(node) for node in range(n)) - 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],
            ],
        )
    )

Prints

-1

3

---

Note:

• We can add more details about other issues in your code. But, that's unnecessary.

Answer 2

A simpler solution is to use a disjoint set to keep track of the number of connected components. The number of components starts at n; when merging two distinct sets, the count drops by 1. If an edge connects two already connected nodes, we can track it as an extra edge. At the end, we need enough extra edges to connect all other connected components to a central component to connect the whole graph.

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        par = [*range(n)]
        extra = 0
        comps = n
        def find(x):
            if x != par[x]:
                par[x] = find(par[x])
            return par[x]
        for u, v in connections:
            u, v = find(u), find(v)
            if u == v:
                extra += 1
            else:
                comps -= 1
                par[v] = u
        return -1 if comps - 1 > extra else comps - 1