How many cables are plugged in?

Picture the back of an office network switch. You don't care where each cable goes; you only want to know how many are plugged into each computer. That number is the node's degree.

And here is the nice part: you don't need neighbour lists for it. Every cable adds one plug at each of its two ends. That's it.

Add one to both ends: one pass over the edges, nothing else.

No cables: a computer in no edge keeps degree 0.

In code

deg = [0] * n
for u, v in edges:
    deg[u] += 1
    deg[v] += 1
return deg

4 computers, cables [[0, 1], [0, 2], [2, 3]]

deg: [0, 0, 0, 0]
total: 0

Every computer starts at 0 plugs. The small number under each one is its degree.

Move 1 of 5

A free way to check your work

Add up all the degrees and you always get exactly twice the number of edges, because every cable has two ends. Three cables means the degrees must add up to 6.

If your total comes out odd, some end didn't get counted. Step through below and watch the total climb by 2 with every edge.

Sum of degrees: always twice the number of edges.

Count both ends: adding to only one end gives half the story.