A - Breadth First Search Aizu - ALDS1_11_C

2-Day1—A
Write a program which reads an directed graph $G = (V, E)$ , and finds the shortest distance from vertex $1$ to each vertex (the number of edges in the shortest path). Vertices are identified by IDs $1, 2, ... n$ .

Input
In the first line, an integer $n$ denoting the number of vertices, is given. In the next $n$ lines, adjacent lists of vertex $u$ are given in the following format:

$u$ $k$ $v_1$ $v_2$ ... $v_k$

$u$ is ID of the vertex and $k$ denotes its degree. $v_i$ are IDs of vertices adjacent to $u$ .

Constraints $1 \leq n \leq 100$
Output
For each vertex $u$ , print $id$ and $d$ in a line. $id$ is ID of vertex $u$ and $d$ is the distance from vertex $1$ to vertex $u$ . If there are no path from vertex $1$ to vertex $u$ , print -1 as the shortest distance. Print in order of IDs.

Sample Input 1
4
1 2 2 4
2 1 4
3 0
4 1 3
Sample Output 1
1 0
2 1
3 2
4 1

Reference
Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

思路：跟题目名字一样，写个广搜就行

代码如下：

#include<cstdio>
#include<queue>
#include<cmath>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=101;
int e[maxn][maxn];
int d[maxn];
int n;
void bfs(int s)
{
    queue<int>q;
    q.push(s);
    for(int i=0; i<n; i++)
        d[i]=-1;
    d[s]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int v=0; v<n; v++)
        {
            if(e[u][v]==0)
                continue;
            if(d[v]!=-1)continue;
            d[v]=d[u]+1;
            q.push(v);
        }
    }
    for(int i=0; i<n; i++)
        cout<<i+1<<" "<<((d[i]==-1)?(-1):d[i])<<endl;
}
int main()
{
    int u,k,v;
    cin>>n;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            e[i][j]=0;
    for(int i=0; i<n; i++)
    {
        cin>>u>>k;
        u--;
        for(int j=0; j<k; j++)
        {
            cin>>v;
            v--;
            e[u][v]=1;
        }
    }
    bfs(0);
    return 0;
}