Baku Metro (Editorial)

The metro map is a connected undirected graph with $n$ vertices and $n$ edges. A connected graph on $n$ vertices with exactly n - 1 edges is a tree. Adding one more edge to a tree creates exactly one cycle. Therefore, the graph in the problem consists of a single cycle (the ring line), with trees (possibly empty) attached to its vertices.

For each vertex, we need to find the length of the shortest path to the nearest vertex of the cycle. For vertices on the cycle, the answer is $0$. The problem is solved in two stages.

Stage 1. Finding the cycle: repeated removal of leaves

Compute the degrees of all vertices. Push all vertices of degree $1$, that is, the leaves, into a queue. While the queue is not empty, pop a vertex $v$ from it and mark it as removed. Then decrease by $1$ the degree of each of its neighbors that has not yet been removed. If a neighbor's degree becomes $1$, it has turned into a leaf itself, so we push it into the queue.

When the process finishes, only the cycle vertices remain unremoved. This follows from two observations:

• A cycle vertex never becomes a leaf. It always has two neighbors on the cycle, and those are never removed either. This can be proved rigorously by induction on the steps of the process.

• Every vertex of an attached tree gets removed. Leaf removal "peels" the tree from the bottom up, from the leaves toward the point where the tree is attached to the cycle. This procedure is analogous to topological sorting with Kahn's algorithm, only applied to an undirected graph.

Stage 2. Multi-source breadth-first search

Set d[v] = 0 for all cycle vertices and d[v] = –1 (not visited) for all other vertices. Push all cycle vertices into the queue at once and run a breadth-first search from them. When a vertex $u$ is popped from the queue, each of its unvisited neighbors $w$ gets d[w] = d[u] + 1 and is pushed into the queue.

A breadth-first search from a set of sources processes vertices in non-decreasing order of their distance to that set. Therefore, $d[v]$ equals the minimum number of moves from $v$ to the ring line. Since everything outside the cycle is a tree, the path from each station to the ring is in fact unique.

Example

In the first example, all vertices are part of a single cycle, so the distance for each of them is $0$.

In the second example, the cycle consists of vertices $2,3$, and $5$, while the remaining vertices are located at some distance from it.

Algorithm implementation

Declare the adjacency list of the graph $g$ and the auxiliary arrays:

• $used$ — the removal flag of a vertex: used[v] = 1 if vertex $v$ has already been removed as a leaf, and used[v] = 0 if it is still in the graph. After the first stage, zero values remain only for the cycle vertices;

• $dist$ — the array of distances: dist[v] equals the number of moves from vertex $v$ to the nearest cycle vertex (the value $–1$ means that the vertex has not been visited yet);

• $deg$ — the current vertex degrees: deg[v] equals the number of neighbors of vertex $v$ that have not been removed yet.

The queue $q$ is used in both stages of the algorithm: first for the repeated removal of leaves, then for the multi-source breadth-first search.

vector<vector<int> > g;
vector<int> used, dist, deg;
queue<int> q;

Read the input data. Build the graph.

scanf("%d", &n);
g.resize(n + 1);
for (i = 0; i < n; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  g[b].push_back(a);
}

Compute the initial degrees of the vertices: the degree of vertex $i$ equals the size of its adjacency list $g[i]$. Push all leaves, that is, vertices of degree $1$, into the queue $q$ and immediately mark them as removed (used[i] = 1).

used.resize(n + 1, 0);
deg.resize(n + 1, 0);
for (i = 1; i <= n; i++)
{
  deg[i] = g[i].size();
  if (deg[i] == 1)
  {
    q.push(i);
    used[i] = 1;
  }
}

Remove the leaves one by one. Outwardly this loop resembles a breadth-first search, but a vertex is pushed into the queue not when it is first discovered, but only when it becomes a leaf itself. Pop a vertex $v$ from the queue and iterate over its neighbors $to$. Neighbors already marked as removed are skipped. For each neighbor that has not been removed, decrease its degree by $1$, since the edge (v, to) disappears from the graph together with vertex $v$.

while (!q.empty())
{
  int v = q.front(); q.pop();
  for (int to : g[v])
    if (used[to] == 0)
    {
      deg[to]--;

If after the decrease the degree of vertex $to$ has become $1$, then it has only one neighbor left that has not been removed, so it has turned into a leaf itself. Push it into the queue and mark it as removed. Cycle vertices never reach degree $1$, so the process stops at the ring line.

      if (deg[to] == 1)
      {
        q.push(to);
        used[to] = 1;
      }
    }
}

At this point the equality used[i] = 0 holds if and only if vertex $i$ belongs to the cycle.

Initialize the array $dist$ with the value $–1$ (no vertex has been visited). The queue is already empty at this point, but assigning an empty queue explicitly resets it before the second traversal.

dist = vector<int>(n + 1, -1);
q = queue<int>();

Then push every cycle vertex into the queue and set dist[i] = 0 for it — all vertices of the ring line simultaneously become the sources of the breadth-first search.

for (i = 1; i <= n; i++)

  if (used[i] == 0)
  {
    q.push(i);
    dist[i] = 0;
  }

Run the multi-source breadth-first search. Pop a vertex $v$ from the queue. Each of its unvisited neighbors to~(dist[to] = –1) gets the distance dist[v] + 1 and is pushed into the queue. Cycle vertices are marked with distance $0$ from the very beginning, so the traversal never returns to the ring and spreads only into the attached trees. Since vertices are popped from the queue in non-decreasing order of distance, each value dist[to] is the shortest one.

while (!q.empty())
{
  int v = q.front(); q.pop();
  for (int to : g[v])
    if (dist[to] == -1)
    {
      q.push(to);
      dist[to] = dist[v] + 1;
    }
  }

Print the distances from the stations to the ring line in the order of their numbers.

for (i = 1; i <= n; i++)
   printf("%d ", dist[i]);
printf("\n");