number_of_connected_components_in_an_undirected_graph
1from collections import defaultdict 2 3 4# @leet start 5class Solution: 6 def countComponents(self, n: int, edges: list[list[int]]) -> int: 7 """ 8 This problem asks us to count the connected components in an undirected 9 graph. To do this, we first turn the representation into one that allows 10 for fast access to a node's neighbors, a hashmap of node -> list[node]. 11 12 Afterwards, we iterate through the nodes (given as n) and then dfs through. 13 We return 0 if the node was already visited, or 1 if not and visit all 14 of its neighbors, taking care to add the node to visited if it wasn't 15 already there to avoid cycles. 16 17 We then return the sum of the nodes. 18 """ 19 graph = defaultdict(list) 20 visited = set() 21 22 for a, b in edges: 23 graph[a].append(b) 24 graph[b].append(a) 25 26 def dfs(node): 27 if node in visited: 28 return 0 29 visited.add(node) 30 for neighbor in graph[node]: 31 dfs(neighbor) 32 return 1 33 34 return sum(dfs(i) for i in range(n)) 35 36 37# @leet end 38 39 40def test(): 41 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def countComponents(self, n: int, edges: list[list[int]]) -> int: 8 """ 9 This problem asks us to count the connected components in an undirected 10 graph. To do this, we first turn the representation into one that allows 11 for fast access to a node's neighbors, a hashmap of node -> list[node]. 12 13 Afterwards, we iterate through the nodes (given as n) and then dfs through. 14 We return 0 if the node was already visited, or 1 if not and visit all 15 of its neighbors, taking care to add the node to visited if it wasn't 16 already there to avoid cycles. 17 18 We then return the sum of the nodes. 19 """ 20 graph = defaultdict(list) 21 visited = set() 22 23 for a, b in edges: 24 graph[a].append(b) 25 graph[b].append(a) 26 27 def dfs(node): 28 if node in visited: 29 return 0 30 visited.add(node) 31 for neighbor in graph[node]: 32 dfs(neighbor) 33 return 1 34 35 return sum(dfs(i) for i in range(n))
def
countComponents(self, n: int, edges: list[list[int]]) -> int:
7 def countComponents(self, n: int, edges: list[list[int]]) -> int: 8 """ 9 This problem asks us to count the connected components in an undirected 10 graph. To do this, we first turn the representation into one that allows 11 for fast access to a node's neighbors, a hashmap of node -> list[node]. 12 13 Afterwards, we iterate through the nodes (given as n) and then dfs through. 14 We return 0 if the node was already visited, or 1 if not and visit all 15 of its neighbors, taking care to add the node to visited if it wasn't 16 already there to avoid cycles. 17 18 We then return the sum of the nodes. 19 """ 20 graph = defaultdict(list) 21 visited = set() 22 23 for a, b in edges: 24 graph[a].append(b) 25 graph[b].append(a) 26 27 def dfs(node): 28 if node in visited: 29 return 0 30 visited.add(node) 31 for neighbor in graph[node]: 32 dfs(neighbor) 33 return 1 34 35 return sum(dfs(i) for i in range(n))
This problem asks us to count the connected components in an undirected graph. To do this, we first turn the representation into one that allows for fast access to a node's neighbors, a hashmap of node -> list[node].
Afterwards, we iterate through the nodes (given as n) and then dfs through. We return 0 if the node was already visited, or 1 if not and visit all of its neighbors, taking care to add the node to visited if it wasn't already there to avoid cycles.
We then return the sum of the nodes.
def
test():