Given an undirected graph as an adjacency list, return the number of edges.
Remember that an undirected edge a–b shows up in both a's and b's neighbour
lists, so the raw count of neighbour entries is double the number of edges.
countEdges(graph)
Input format: a,b edge pairs separated by spaces (the graph is built for you,
undirected).
a,b a,c b,d // → 3
a,b // → 1
(no edges) // → 0
This is about noticing a bit of double-counting baked into how undirected graphs are represented. An edge between a and b is stored twice — once as a in b's list, once as b in a's — so you have to be careful what you're actually counting when you tally neighbour-list lengths.
A tempting first move: "every node's degree tells me how many edges touch it, so summing all degrees gives me the total edges." Almost right, but it gives twice the number of edges. Each edge contributes 1 to each of its two endpoints' degrees, so it's counted once from each side.
Once you see the double-count is uniform — every edge counted exactly twice, no exceptions — the fix is immediate: sum every node's neighbour-list length (the sum of all degrees), then divide by two.
You could enumerate each unique edge once — say, only counting a→b when a comes before b alphabetically. That works too, but needs extra bookkeeping for no real benefit. "Sum then halve" sidesteps all of that: no ordering or identity comparisons, just a total count from one pass.
Sometimes the fastest route to an answer isn't to carefully avoid overcounting, but to overcount in a predictable, uniform way and correct for it afterward with simple arithmetic. The "error" here is constant and easy to reverse, which keeps the solution simple and fast.
def count_edges(graph):
total = 0
for node in graph:
total += len(graph[node])
return total // 2
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.