Count the connections
Every edge adds one to the degree of both of its ends. About 7 minutes.
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.
deg = [0] * n
for u, v in edges:
deg[u] += 1
deg[v] += 1
return deg- deg
- [0, 0, 0, 0]
- total
- 0
Every computer starts at 0 plugs. The small number under each one is its degree.
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.
A graph has 5 edges. What do its degrees add up to?
- A10
- B5
- CIt depends on the number of nodes
Show the answer
10. Each edge adds 1 at each end: 5 × 2 = 10.
Count the connections
A network has n computers numbered 0 to n - 1, and each cable [u, v] in edges joins computers u and v. Return a list whose i-th number is how many cables are plugged into computer i.
n = 4, edges = [[0, 1], [0, 2], [2, 3]] → [2, 1, 2, 1]
1 ≤ n ≤ 100,000 · 0 ≤ edges.length ≤ 100,000 · 0 ≤ u, v < n · no edge joins a node to itself and no edge appears twice