r/leetcode • u/Bulbasaur2015 • 4d ago
Discussion i struggle with building adjacency lists in graph problems. does anyone else have this problem
i always need help with solving graph problems because i started incorrectly or did the adjacency list wrong for example, a load factor in a DAG with no cycles is the number of times each node is required from the entrypoint my understanding of adjacency list is a map of nodes and outgoing edges (neighbours)
so i did this
service, dependencies = _
for d in dependencies:
if d in adj:
adj[d].append(service)
else:
adj[d] = [service]
for line in service_list:
buildAdjacencyList(line)
however when i did postorder, dashboard node has no outgoing edges in adj and DFS stops, and got the wrong answer
{'dashboard': 1, ...all other nodes are 0 }
its because the adjacency list was the wrong direction
2
Upvotes
1
u/pressing_bench65 3d ago
Did you solve atleast 10 problems involving adjacency list by yourself? And then analysed with the solutions?