Find connected component in undirected graph. Each node in the graph contains a label and a list of its neighbors. this is the link: https://www.lintcode.com/problem/431/ Leetcode requires membership for this question.
class UndirectedGraphNode:
def __init__(self, x):
self.label = x
self.neighbors = []
I solved it this way but it returns []
class Solution:
def connectedSet(self, nodes):
res=[]
visited=set()
def dfs(node,path):
if not node:
res.append(path.copy())
return
if node in visited:
return
visited.add(node)
for neighbor in node.neighbors:
if neighbor not in visited:
print(path)
dfs(neighbor,path [node.label])
for node in nodes:
if node not in visited:
dfs(node,[])
return res
This returns []. I belive its logic correct. Run depth first search checking if the node is not visited, till no node exists.
Input Data
{1,2,4#2,1,4#3,5#4,1,2#5,3}
Expected Result
[[1,2,4],[3,5]]
Result
[]
CodePudding user response:
Your condition if not node:
doesn't make sense: you're not modifying nodes or making them Falsey. Depth first search explores a forest of rooted trees. Your outer loop over nodes looks for the roots of these trees, so you should just pass a reference to an empty list into dfs
, to track all the nodes explored in the search tree for that root:
class Solution:
def connectedSet(self, nodes):
res = []
visited = set()
def dfs(node, path):
path.append(node.label)
visited.add(node)
for neighbor in node.neighbors:
if neighbor not in visited:
dfs(neighbor, path)
for node in nodes:
if node not in visited:
path = []
dfs(node, path)
res.append(sorted(path.copy()))
return res