树与图的广度优先遍历:acwing 847. 图中点的层次

本文主要是介绍树与图的广度优先遍历:acwing 847. 图中点的层次，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include<bits/stdc++.h>
using namespace std;const int N=1e5+10;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N];void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}int bfs()
{memset(d,-1,sizeof d);queue<int> q;d[1]=0;q.push(1);while(q.size()){int t=q.front();q.pop();for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(d[j]==-1){d[j]=d[t]+1;q.push(j);}}}return d[n];
}int main()
{memset(h,-1,sizeof h);scanf("%d%d",&n,&m);for(int i=0;i<m;i++){int a,b;scanf("%d%d",&a,&b);add(a,b);}printf("%d\n",bfs());return 0;
}

最短路使用bfs，建立链表使用这个代码模板

void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bfs算法的模板

int bfs()
{memset(d,-1,sizeof d);queue<int> q;d[1]=0;q.push(1);while(q.size()){int t=q.front();q.pop();for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(d[j]==-1){d[j]=d[t]+1;q.push(j);}}}return d[n];
}

注意需要把链表头初始化，不然会超时 

 

 

这篇关于树与图的广度优先遍历:acwing 847. 图中点的层次的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---