Where it runs
1. The problem
In the last group of lessons you worked with trees: a root, children under it, and one clear path down to any node. A tree is a graph with no cycles (no loops), where there is exactly one path between any two nodes. A general graph promises neither. Connections can close into a loop, and between two nodes there can be many paths or none at all.
Almost everything in real life is a graph: cities and the roads between them, people who follow each other, web pages that link to each other in circles, tasks that wait for other tasks. None of it fits a tree, where links only go from top to bottom.
Before you can walk a graph, look for the shortest path or count its parts, you have to store it in memory. This lesson is only about that: how to store the nodes and the connections so the next algorithms have something to read.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Graph problems where the answer comes from who connects to whom, such as degrees and direct links. Build the adjacency list once, and count incoming and outgoing edges when needed.
The center is the node with degree n minus 1, and it is the node the first two edges share.
Count incoming and outgoing edges, and the judge has n minus 1 in and 0 out.
Add the degrees of every pair of cities, minus 1 when the two are linked directly, which a set of edges answers in O(1).
The answer is every node with no incoming edge, since nothing else can reach it.