Python Construct Graph -> BFS


  • 0
    class GraphNode:
        def __init__(self, value):
            self.val = value
            self.neighbors = []
            
            
    class Solution(object):
        def countComponents(self, n, edges):
            nodes = {i:GraphNode(i) for i in range(n)}
            for x, y in edges:
                nodes[x].neighbors.append(y)
                nodes[y].neighbors.append(x)
            count = 0
            while len(nodes) > 0:
                count += 1
                queue = [nodes.popitem()[1]]
                while queue:
                    new_queue = []
                    for node in queue:
                        for y in node.neighbors:
                            if y in nodes:
                                new_queue.append(nodes[y])
                                del nodes[y]
                    queue = new_queue
            return count

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.