dfs與bfs常用模板
2024-09-06 07:00:35
基本遍歷：
//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;
}
最新文章
- Ubuntu16.04安装Samba
- 20151208Study
- HDU 4865 Peter's Hobby（概率、dp、log）
- 删除表数据drop、truncate和delete的用法
- 将数组里的元素拼接成sql里的in条件
- (Stack)Basic Calculator I && II
- 第九讲：HTML5该canvas推箱子原型实现
- STM32驱动DHT11温湿度传感器
- 1.centOS安装Mysql
- Shell和命令基础
- sum() 函数性能堪忧，列表降维有何良方？
- Springboot2注解使用Mybatis动态SQL
- vue_drf之支付宝接口
- [原]Jenkins(十八) jenkins再出发之jenkins 内置变量
- time&datetime模块详解
- 注意：Tomcat Get请求的坑！
- linux学习笔记-conky配置开机启动方法
- 在webstorm中配置sass环境
- ios中UIWebview和asiHttprequest的用法
- Python学习之路：一天搞定基础部分