图的开始--第二天打卡之图的遍历(bfs)
作者:
lgd123
,
2021-07-26 10:24:15
,
所有人可见
,
阅读 234
----------
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 105;
int m[N][N];
int d[N],n;
void bfs(int s)
{
queue<int> q;
q.push(s);
memset(d,-1,sizeof(d));
d[s]=0;
while(!q.empty())
{
int u;
u = q.front();q.pop();
for(int i=0;i<n;i++)
{
if(m[u][i]==0) continue;
if(d[i]!=-1) continue;
d[i]=d[u]+1;
q.push(i);
}
}
for(int i=0;i<n;i++)
{
if(d[i]==-1) cout<<i+1<<" "<<-1<<endl;
else cout<<i+1<<" "<<d[i]<<endl;
}
}
int main()
{
int u,v,k;
cin>>n;
memset(m,0,sizeof(m));
for(int i=0;i<n;i++)
{
cin>>u>>v;
u--;
for(int j=0;j<v;j++)
{
cin>>k;
k--;
m[u][k]=1;
}
}
bfs(0);
return 0;
}