说明

• 对于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:真的这样结束了嘛?

脑洞:若求所能到达的节点编号最小???

在无向图中???

大坑待填。

最新文章

  1. filesort是通过相应的排序算法
  2. mysql学习(3)-linux下mysql主从复制
  3. 关于printf函数的所思所想
  4. haproxy+keepalived实现高可用负载均衡
  5. struts2:JSP页面及Action中获取HTTP参数(parameter)的几种方式
  6. 对Map按key和value分别排序
  7. DS18B20 for STM32 源代码 【worldsing笔记】
  8. 教你50招提升ASP.NET性能(二):移除不用的视图引擎
  9. bzoj1558
  10. Linux企业级开发技术(3)——epoll企业级开发之epoll模型
  11. 【破解】破解ACDSEE15的方法
  12. c# 小数的处理
  13. 【HELLO WAKA】WAKA iOS客户端 之一 APP分析篇
  14. 深入理解javascript函数进阶系列第二篇——函数柯里化
  15. Yii2 解决2006 MySQL server has gone away问题
  16. 数据库sql常见优化方法
  17. Kali Linux搭建Go语言环境
  18. Win10使用VNC连接Centos7远程桌面
  19. SpringMVC Controller 返回值几种类型
  20. Oracle RMAN备份与还原注意事项

热门文章

  1. java数据结构和算法09(哈希表)
  2. 【网络】TCP的拥塞控制
  3. Eclipse luna 装不上 veloeclipse
  4. 关于OutOfMemoryError的处理
  5. Win32 Windows编程 七
  6. 2015/12/29 eclipse 设置要点 空间 项目 类 eclipse汉化
  7. CodeChef - CHEFPRAD Chef and Pairs 树形DP
  8. 在做java 的web开发,为什么要使用框架
  9. cocos2dx笔记1:概述
  10. HDU1166 敌兵布阵 —— 线段树单点修改