Clinic #26: Redundant Connection

Dots and the lines between them, and in its last panel the tool this clinic is about: every dot points at another dot, the one at the top of each chain names the group, and two short questions (“walk up to the top”, “point one top at the other”) answer whether two dots are already joined.

Before you start. A graph is a set of dots joined by lines; Graphs (BFS, DFS, Dijkstra, topological sort) builds it from scratch, and here the dots are houses and the lines are cables. Engineers write the cost of reading every item in a list once as O(n), said “order n”: double the list, double the work. A full walk of the list for every item is O(n²): double the list, four times the work, and at ten thousand items a hundred million steps.