编程开发 购物 网址 游戏 小说 歌词 地图 快照 股票 美女 新闻 笑话 | 汉字 软件 日历 阅读 下载 图书馆 开发 租车 短信 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
移动开发 架构设计 编程语言 互联网 开发经验 Web前端 开发总结
开发杂谈 系统运维 研发管理 数据库 云 计 算 Java开发
VC(MFC) Delphi VB C++(C语言) C++ Builder 其它开发语言 云计算 Java开发 .Net开发 IOS开发 Android开发 PHP语言 JavaScript
ASP语言 HTML(CSS) HTML5 Apache MSSQL数据库 Oracle数据库 PowerBuilder Informatica 其它数据库 硬件及嵌入式开发 Linux开发资料
  编程开发知识库 -> 编程语言 -> 洛谷P3916 图的遍历_graph -> 正文阅读
 

[编程语言]洛谷P3916 图的遍历_graph[第1页]

题目描述
给出NN个点,MM条边的有向图,对于每个点vv,求A(v)A(v)表示从点vv出发,能到达的编号最大的点。
输入输出格式 输入格式:
第1 行,2 个整数N,MN,M。
接下来MM行,每行2个整数U_i,V_iUi?,Vi?,表示边(U_i,V_i)(Ui?,Vi?)。点用1, 2,\cdots,N1,2,?,N编号。
输出格式:
N 个整数A(1),A(2),\cdots,A(N)A(1),A(2),?,A(N)。
输入输出样例
输入样例#1: 

4 3
1 2
2 4
4 3

输出样例#1: 

4 4 3 4

说明
? 对于60% 的数据,1 \le N . K \le 10^31≤N.K≤103;
? 对于100% 的数据,1 \le N , M \le 10^51≤N,M≤105。
本来是想用 暴力深搜 ,结果莫名爆炸,然后就弃疗了。。。
看了题解,发现可以用深搜,从后往前搜反向图。
附代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 100010
using namespace std;
int n,m,c=1,head[MAXN],maxn[MAXN];
struct node{
	int next,to;
}a[MAXN<<1];
inline int read(){
       int date=0,w=1;char c=0;
       while(c<'0'|c>'9'){if(c=='-')w=-1;c=getchar();}
       while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
       return date*w;
}
void add(int x,int y){
	a[c].to=y;
	a[c].next=head[x];
	head[x]=c++;
}
void dfs(int x,int rt){
	if(maxn[x])return;
	int v;
	maxn[x]=rt;
	for(int i=head[x];i;i=a[i].next){
		v=a[i].to;
		if(!maxn[v])
		dfs(v,rt);
	}
}
int main(){
	int x,y;
	n=read();m=read();
	for(int i=1;i<=m;i++){
		x=read();y=read();
		add(y,x);
	}
	for(int i=n;i>=1;i--)dfs(i,i);
	for(int i=1;i<=n;i++)printf("%d ",maxn[i]);
	printf("\n");
	return 0;
}

阅读全文
版权声明:本文为博主原创文章,未经博主允许不得转载。
本文已收录于以下专栏:

发表评论
HTML/XML objective-c Delphi Ruby PHP C# C++ JavaScript Visual Basic Python Java CSS SQL 其它
相关文章推荐
洛谷OJ - P1087 FBI树 ( 后序遍历 )
题目描述 我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,既含“0”又含“1”的串则称为F串。 FBI树是一种二叉树,它的结点类型也包括F结点,B结点和I结点...
qq_34594236 2017-03-18 16:23 181 洛谷 P2335 [SDOI2005]位图
炒鸡简单的BFS, 把白色的先入队列,然后慢慢往外扩。 BFS保证第一次触到一个点时,总是距离最近的。 #include using namespace std; int n,m; s...
Blackieonly 2016-10-15 12:26 109 洛谷P1598 垂直柱状图
这个题目比较坑爹啊,就是输出有着很严格的限制,不能有多余的空格,不能有多余的空行。 本来我是想直接输出的,发现不能一竖列一竖列地输出。好吧,想起用二维数组,又发现要从下往上输出星号。j--倒过来就行了...
YiQ_Wang 2016-07-08 16:42 183 P1598 垂直柱状图(洛谷)
题目描述 写一个程序从输入文件中去读取四行大写字母(全都是大写的,每行不超过72个字符),然后用柱状图输出每个字符在输入文件中出现的次数。严格地按照输出样例来安排你的输出格式。 输入输出格式 输...
huihao123456 2017-01-30 20:40 81 【NOIP2009】洛谷P1073 最优贸易(SPFA + 反向建图)
题目描述 C 国有 n 个大城市和 m 条道路,每条道路连接这 n 个城市中的某两个城市。任意两个 城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路,一部分 ...
Loi_Meiko 2016-11-11 21:13 177 图(Graph)——基本概念、存储、遍历
. 图的基本概念 图(Graph):G = ( V,E ) V(G):顶点 E(G):边 (1)边: (2)权:与图的边或弧相关的个数 (3)子图:如果图G(V,E...
J__King 2014-09-23 08:59 778 洛谷 P2335 [SDOI2005]位图 [DP]
图上递推线性可曲DP, k->n+m的原因是因为最坏情况为对角线为递推线路。#include #include #include #include using namespace std; char...
lemonoil 2017-07-22 17:24 105 【数据结构】图Graph的邻接矩阵,邻接表及深度、广度遍历
图的分类 有/无向图 如果给图的每条边规定一个方向,那么得到的图称为有向图。在有向图中,与一个节点相关联的边有出边和入边之分。相反,边没有方向的图称为无向图。 下面介绍图的两种存储结构 1、...
shangguan_1234 2016-11-27 16:40 1038 洛谷 P2452 [SDOI2005]屠龙传说-屠龙枪卷 [计算几何]
题目连接就一个所点与延展的算计基本题,主要是eps很迷,SDOI防AC题,线下70分,线上0分,暂且发一下垃圾code#include #include #include #include #incl...
lemonoil 2017-07-22 17:34 116 洛谷P1052 过河
读完题目想到的应该是动态规划,状态转移方程为f[i]=min(f[i],f[j]+v[i]) (v[]表示当前点的石头,j∈[i-s,i-t]),但是转移的是每个点,而数据范围有1000000000那...
Cliu__ 2017-07-20 17:48 178
yangrui2002 +关注
原创 63 粉丝 0 喜欢 0 码云  
他的最新文章 更多文章
忧桑三角形 洛谷P3916 图的遍历_graph 洛谷P1559 运动员最佳匹配问题 洛谷P1440 求m区间内的最小值
在线课程

【免费】搜狗机器翻译技术分享
讲师:

深度学习在推荐领域的应用和实践
讲师:吴岸城
热门文章 肥得更高
520
洛谷P1546 最短网络 Agri-Net
357
洛谷P2504 [HAOI2006]聪明的猴子
209
洛谷P1558 色板游戏
205
洛谷P2951 [USACO09OPEN]捉迷藏Hide and Seek
166
0
  编程语言 最新文章
洛谷P3916 图的遍历_graph
Java_7
C#使用UdpClient发送和接收UDP数据示例 16进
php必会基础
Java判断是否为整数的5种方法
Socket 双向传输问题
腾讯手QQ核心技术-NDK开发语音消息变声功能
遍历枚举接口的元素
多线程-ThreadLocal
翻译 Spring Boot How To
上一篇文章           查看所有文章
加:2017-10-30 04:01:06  更:2017-10-30 04:03:09 
VC(MFC) Delphi VB C++(C语言) C++ Builder 其它开发语言 云计算 Java开发 .Net开发 IOS开发 Android开发 PHP语言 JavaScript
ASP语言 HTML(CSS) HTML5 Apache MSSQL数据库 Oracle数据库 PowerBuilder Informatica 其它数据库 硬件及嵌入式开发 Linux开发资料
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2018年6日历
2018-6-21 8:44:52
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  编程开发知识库