Luogu P3916 图的遍历 【优雅的dfs】【内有待填坑】By cellur925
2024-08-24 22:57:46
说明
• 对于60% 的数据, n,m在1e3内
• 对于100% 的数据, n,m在1e5内。
本弱弱上来就是一顿暴搜打,dfs n次,每次更新答案,复杂度为O(n*n),果然TLE,60分抱回家。
#include<cstdio>
#include<algorithm>
#include<cstring> using namespace std; int n,m,tot,head[],vis[],f[];
struct node{
int to,next;
}edge[]; void add(int x,int y)
{
edge[++tot].next=head[x];
head[x]=tot;
edge[tot].to=y;
} void dfs(int x)
{
vis[x]=;
for(int i=head[x];i;i=edge[i].next)
{
int v=edge[i].to;
if(vis[v]) continue;
dfs(v);
f[x]=max(f[x],f[v]);
}
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int x=,y=;
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=;i<=n;i++) f[i]=i;
for(int i=;i<=n;i++)
{
dfs(i);
memset(vis,,sizeof(vis));
}
for(int i=;i<=n;i++) printf("%d ",f[i]);
return ;
}
然后就通往了题解。我们可以转化一下思维:求多个点到一个点,不妨从最大的点出发倒着遍历,反向连边,这样每个点只会被访问一次,复杂度O(n).
#include<cstdio>
#include<algorithm>
#include<cstring> using namespace std; int n,m,tot,head[],f[];
struct node{
int to,next;
}edge[]; void add(int x,int y)
{
edge[++tot].next=head[x];
head[x]=tot;
edge[tot].to=y;
} void dfs(int noww,int st)
{
if(f[noww]) return ;
f[noww]=st;
for(int i=head[noww];i;i=edge[i].next)
if(!f[edge[i].to]) dfs(edge[i].to,st);
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int x=,y=;
scanf("%d%d",&x,&y);
add(y,x);
}
for(int i=n;i>=;i--)
dfs(i,i);
for(int i=;i<=n;i++) printf("%d ",f[i]);
return ;
}
ps:真的这样结束了嘛?
脑洞:若求所能到达的节点编号最小???
在无向图中???
大坑待填。
最新文章
- filesort是通过相应的排序算法
- mysql学习(3)-linux下mysql主从复制
- 关于printf函数的所思所想
- haproxy+keepalived实现高可用负载均衡
- struts2:JSP页面及Action中获取HTTP参数(parameter)的几种方式
- 对Map按key和value分别排序
- DS18B20 for STM32 源代码 【worldsing笔记】
- 教你50招提升ASP.NET性能(二):移除不用的视图引擎
- bzoj1558
- Linux企业级开发技术(3)——epoll企业级开发之epoll模型
- 【破解】破解ACDSEE15的方法
- c# 小数的处理
- 【HELLO WAKA】WAKA iOS客户端 之一 APP分析篇
- 深入理解javascript函数进阶系列第二篇——函数柯里化
- Yii2 解决2006 MySQL server has gone away问题
- 数据库sql常见优化方法
- Kali Linux搭建Go语言环境
- Win10使用VNC连接Centos7远程桌面
- SpringMVC Controller 返回值几种类型
- Oracle RMAN备份与还原注意事项