I’m learning graphs and can’t solve this task. As I understand there are 2 conditions for graph being a tree:
-
vertices must be connected
-
there is no cycle
To check for connectivity I am using dfs
graph = []
visited = []
def dfs(v):
visited[v] = True
for u in graph[v]:
if not visited[u]:
dfs(u)
the main function is
def isTree(adj_list):
global graph, visited
n = len(adj_list)
graph = adj_list
visited = [False for i in range(n)]
is_tree = True
# MY CODE STARTS HERE
for v in range(n):
if not visited[v]:
dfs(v)
elif v in graph[-1]:
is_tree = False
# END OF CODE
return is_tree
adj_list = [[1,2], [0], [0]]
print(isTree(adj_list))
I thought condition elif would check for cycling. But it doesn’t look so.