MediumPython ProgrammingHigh School (11–12)High School (9–10)UndergraduateGeneralPython Going Further › Data StructuresConceptualA-Level
A network has the links A to B, B to C, D to E, and F alone…
Contributed by StemPy LabTry it on paper first. A hint, the key idea and the worked solution are here when you need them.
A network has the links A to B, B to C, D to E, and F alone. Store it as a dictionary of neighbours, and use a search to count the separate groups of connected nodes. What is the answer?
The worked solution
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Plan. The groups are A, B, C together; D and E together; F alone. That is 3 groups. To compute it, take each node that is not done yet, find everything reachable from it, and count one group.
Check. Starting at A: reaches A, B and C. Starting at D: D and E. Starting at F: F alone. The count is 3. (This version uses a stack instead of recursion, which is also a depth-first search.)
Answer: 3.
Discussion (0)
Log in to join the discussion.
Loading…