Find number of redundant edges in components of a graph

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.

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

Note:

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

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

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}.")

Filed under: Kiến thức lập trình - @ 18:37

Thẻ: pythonalgorithmgraph-theory

Thiết kế website giá rẻ

Danh mục