dfs與bfs常用模板

谁借莪１个温暖的怀抱￠ 2023-08-17 17:47 91阅读 0赞

基本遍歷：

//dfs void dfs(int x) { v[x]=1; for(int i=head[x];i;i=next[i]) { int y=ver[i]; if(v[y]) continue; dfs(y); } } //bfs void bfs(int x) { queue<int>q; q.push(x);v[x]=1; while(q.size()) { int u=q.front();q.pop(); for(int i=head[u];i;i=next[i]) { int y=ver[i]; if(v[y]) continue; v[y]=1; q.push(y); } } }

dfs求樹和圖的信息

//dfs時間戳 void dfs(int x) { dfn[x]=++cnt; v[x]=1; for(int i=head[x];i;i=next[i]) { int y=ver[i]; if(v[y]) continue; dfs(y); } } //dfs序 void dfs(int x) { dfsx[++cnt]=x; v[x]=1; for(int i=head[x];i;i=next[i]) { int y=ver[i]; if(v[y]) continue; dfs(y); } dfsx[++cnt]=x; } //樹的深度 void dfs(int x) { v[x]=1; for(int i=head[x];i;i=next[i]) { int y=ver[i]; if(v[y]) continue; deep[y]=deep[x]+1; dfs(y); } } //子樹大小+樹的重心 void dfs(int x) { size[x]=v[x]=1; int max_part=0; for(int i=head[x];i;i=next[i]) { int y=ver[i]; if(v[y]) continue; dfs(y); size[x]+=size[y]; max_part=max(max_part,size[y]); } max_part=max(max_part,n-size[x]); if(max_part<ans) { ans=max_part; pos=x; } } //圖的連通塊劃分 void dfs(int x) { v[x]=cnt; for(int i=head[x];i;i=next[i]) { int y=ver[i]; if(v[y]) continue; dfs(y); } } for(int i=1;i<=n;++i) if(!v[i]) { ++cnt; dfs(i); }

bfs求樹和圖的信息

//拓撲排序 void topsort() { queue<int>q; for(int i=1;i<=n;++i) if(deg[i]==0) q.push(i); while(q.size()) { int x=q.front();q.pop(); a[++cnt]=x; for(int i=head[x];i;i=next[i]) if(--deg[ver[i]]==0) q.push(ver[i]); } } int main() { cin>>n>>m; for(int i=1;i<=m;++i) { int x,y; scanf("%d%d",&x,&y); add(x,y); } topsort(); for(int i=1;i<=cnt;++i) printf("%d ",a[i]); return 0; }

转载于:https://www.cnblogs.com/tztqwq/p/11346192.html

发表评论取消回复

表情：

评论列表（有 0 条评论，91人围观）

还没有评论，来说两句吧...

相关阅读

相关 dfs與bfs常用模板

基本遍歷： //dfs void dfs(int x) { v[x]=1; for(int i=head[x];i;i=next[i]) { int y=ver[i]

谁借莪１个温暖的怀抱￠/ 2023年08月17日 17:47/ 0 赞/ 92 阅读

相关 dfs和bfs

https://www.cnblogs.com/wzl19981116/p/9397203.html 1.dfs(深度优先搜索)是两个搜索中先理解并使用的，其实就是暴力把所

àì夳堔傛蜴生んèń/ 2023年03月06日 08:14/ 0 赞/ 16 阅读

相关 DFS&BFS

图的基本介绍前面我们学了线性表和树线性表局限于一个直接前驱和一个直接后继的关系树也只能有一个直接前驱也就是父节点当我们需要表示多对多的关系时，这里我们就用

清疚/ 2023年01月01日 09:52/ 0 赞/ 129 阅读

相关算法 DFS与BFS

一、DFS（深度优先搜索） > DFS: 深度优先遍历DFS与树的先序遍历比较类似。假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点然后依次访问它

傷城~/ 2022年12月20日 03:27/ 0 赞/ 185 阅读

相关 dfs和bfs差别_BFS和DFS之间的区别

![0f76213b219d1be3b9b0f435f8e8bbfd.png][] dfs和bfs差别 Here you will learn about differen

古城微笑少年丶/ 2022年12月07日 13:56/ 0 赞/ 178 阅读

相关 DFS、BFS和Backtracking模板

搜索问题的解法 1. DFS（深度优先搜索） 2. BFS（广度优先搜索） 3. backtracking（回溯） DFS模板 void dfs(.

Bertha 。/ 2022年07月15日 03:43/ 0 赞/ 182 阅读

相关 DFS&&BFS模板

> DFS模板 include<cstdio> include<cstring> include<cstdlib> using names

骑猪看日落/ 2022年06月18日 08:51/ 0 赞/ 194 阅读

相关 DFS和BFS

include<iostream> include<queue> using namespace std; define MAX 100 class MGraph {

谁践踏了优雅/ 2022年06月15日 03:20/ 0 赞/ 185 阅读

相关模板--bfs和dfs

\[cpp\] [view plain][] [copy][view plain] [print][view plain][?][view plain]

小灰灰/ 2022年06月11日 04:17/ 0 赞/ 186 阅读

相关 HDOJ 1312 DFS&BFS

Red and Black Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Jav

雨点打透心脏的1/2处/ 2022年03月31日 03:57/ 0 赞/ 188 阅读