An undirected graph has n vertices, numbered 0 to n - 1, and m edges. For every vertex, print the fewest number of edges on a path from vertex 0 to it, or -1 if it cannot be reached.
What to build
A breadth-first search from vertex 0 that records the distance to each vertex.
Requirements
- Store the graph, with each edge in both directions.
- Use a queue, and give each vertex its distance when it first enters the queue.
- Print -1 for any vertex that is never reached.
Input
The first line has n and m (1 ≤ n ≤ 100, 0 ≤ m ≤ 1000). Each of the next m lines has an edge u v.
Output
The n distances, in vertex order, separated by spaces.
Constraints
1 ≤ n ≤ 100 and 0 ≤ m ≤ 1000.
Example
Input:
6 6
0 1
0 2
1 3
2 4
3 5
4 5
Output:
0 1 1 2 2 3
Why it works
Breadth-first search visits every vertex at distance d before any at distance d + 1, so the first time it reaches a vertex is by a shortest path.
Examples
6 6 0 1 0 2 1 3 2 4 3 5 4 5
0 1 1 2 2 3
3 1 1 2
0 -1 -1
Hints
Hint 1
Store the graph in an adjacency matrix int adj[100][100].
Hint 2
Start every distance at -1 (not seen), set dist[0] = 0 and put 0 in a queue.
Hint 3
Take vertices from the queue; each neighbour v with dist[v] == -1 gets dist[u] + 1 and joins the queue.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int adj[100][100];
int main(void) {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
adj[u][v] = adj[v][u] = 1;
}
int dist[100];
for (int i = 0; i < n; i++) dist[i] = -1;
int queue[100], front = 0, rear = 0;
dist[0] = 0;
queue[rear++] = 0;
while (front < rear) {
int u = queue[front++];
for (int v = 0; v < n; v++) {
if (adj[u][v] && dist[v] == -1) {
dist[v] = dist[u] + 1;
queue[rear++] = v;
}
}
}
for (int i = 0; i < n; i++) {
if (i > 0) printf(" ");
printf("%d", dist[i]);
}
printf("\n");
return 0;
}