题意:
在一个无向图中,能否按照一定的顺序访问图中的某些点,并且能访问的图中的所有的点
大致解法:
先dfs一遍这个图是否强连通
再用bfs判断这个图能否从标记的第1个点走到第k个点
bfs的时候有一点要注意一下
我一开始用的是普通的bfs,设一个值vvv,遇到一个标记点则vvv++,用这种办法bfs其实是错的,比如如下样例输出将是no
#include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; const int nMax = 100007; const int mMax = 400008; int n,m,nk,vis[nMax]; int smark[nMax],sum,marksort[nMax],vvv; class edge{ public: int v,nex; };edge e[mMax]; int k,head[nMax]; void addedge(int a,int b){ e[k].v=b; e[k].nex=head[a]; head[a]=k;k++; } void dfs(int loc){ vis[loc]=1; sum++; for(int i=head[loc];i;i=e[i].nex){ int v=e[i].v; if(!vis[v])dfs(v); } } bool bfs(){ queue<int>que; int i,cv; memset(vis,0,sizeof(vis)); vis[marksort[0]]=1; for(int is=0;is<nk;is++){ if(vis[marksort[is]]==0)return 0; smark[marksort[is]]=0; que.push(marksort[is]); while(!que.empty()){ int v=que.front(); que.pop(); for(i=head[v];i;i=e[i].nex){ cv=e[i].v; if(!vis[cv]){ if(smark[cv]==0){ vis[cv]=1; que.push(cv); }else{ vis[cv]=1; } } } } } return 1; } int main(){ int casenum,i,ffa,ffb; cin>>casenum; while(casenum--){ cin>>n>>m>>nk; memset(smark,0,sizeof(smark)); for(i=0;i<nk;i++){ cin>>ffa; smark[ffa]=1; } k=1; memset(head,0,sizeof(head)); for(i=0;i<m;i++){ cin>>ffa>>ffb; addedge(ffa,ffb); addedge(ffb,ffa); } cin>>ffa; for(i=0;i<ffa;i++){ cin>>marksort[i]; } if(ffa<nk){ cout<<"No\n"; continue; } sum=0; memset(vis,0,sizeof(vis)); dfs(1); if(sum!=n){ cout<<"No\n"; continue; } if(bfs())cout<<"Yes\n"; else cout<<"No\n"; } return 0; }
相关推荐
ACM_DFS+BFS
DFS+BFS深度+广度优先遍历.cpp
算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS 算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS 算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS 算法面试通关40讲完整课件 27-31 深度...
图的相关算法比较全面的总结,包括了图的深度和广度遍历算法,prim和kruskal两种最小生成树的算法,邻接矩阵和邻接表两种储存结构,做课程设计、实验报告或者数据结构学习者可以参考参考啊``源代码都是我亲手打的,...
1.包含了8个文档。 2.大部分为集训队文档。 3.部分算法详解文档。 4.文库搜索,全部下载需要十几分。
标准C的图的实现+BFS和DFS遍历+Dijkstra算法+Prim算法+Kruskal算法实现,纯手写!下载后如有疑问可以私信联系!全部手撸,一键运行,都封装成函数了,易读性很强
列表实现岛屿数量(DFS+BFS) ** 给定一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被...
DFS和BFS DFS(Depth-First-Search)深度优先搜索算法,是搜索算法的一种。是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点 宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法...
动态内存+BFS #include #include #include #include using namespace std; void BFS(list<int> *the_a,int the_N,int the_S,int *the_b){ int *m=new int[the_N]; for(int k1=0;k1;k1++) m[k1]=0; m[the_S-1]=1; ...
定义采用邻接矩阵存储的图结构封装DFS、BFS算法
基于邻接表存储的图的dfs与bfs遍历,对学习数据结构很有帮助
封装DFS、BFS算法、Prim算法、Kruskal算法、Dijstra算法、Floyd算法 上机作业: 定义采用邻接矩阵存储的图结构
用邻接矩阵来存储图,Floyed算法求任意两点间的最短路径并输出,广度优先遍历,深度优先遍历
重传Java实现DFS,BFS,上次传的没有成功,导致几位朋友下了没看到东西。
实验内容及要求: 用字符文件提供数据建立连通无向图...编写程序,实现DFS与BFS算法,输出DFS与BFS生成树的每条边。(边用顶点序号组成的无序偶表示) 实验目的:掌握图的邻接表存储结构;掌握图的遍历算法与生成树。
图的遍历方式包括DFS BFS,这个工程文件是俩种遍历方式的实现,适合学习用,工程实践还得加工,具体分析 在我的博客 数据结构练习 10
dfs-bfs-master 网上找到的 dfs和bfs演示
数据结构中重要的部分之一——图,这里主要完成一个无向无环图的建立,然后进行DFS BFS的遍历,输出结果,初学图和DFS BFS的小伙伴可以来看看噢
基于DFS和BFS广度优先搜索算法的路线搜索算法仿真+含代码操作演示视频 运行注意事项:使用matlab2021a或者更高版本测试,运行里面的Runme.m文件,不要直接运行子函数文件。运行时注意matlab左侧的当前文件夹窗口...
DFS和BFS算法的实现,使用C++语言,适合数据结构初学者学习。