P3916 图的遍历 题目描述
给出 N 个点&＃xff0c; M 条边的有向图&＃xff0c;对于每个点 v &＃xff0c;求 A(v) 表示从点 v 出发&＃xff0c;能到达的编号最大的点。
输入输出格式
输入格式&＃xff1a;
第1 行&＃xff0c;2 个整数 N,MN,M 。
接下来 M 行&＃xff0c;每行2个整数 U_i,V_i&＃xff0c;表示边 (U_i,V_i)。点用 1,2,⋯,N 编号。
输出格式&＃xff1a;
N 个整数 A(1),A(2),⋯,A(N) 。
输入输出样例
4 3
1 2
2 4
4 3
4 4 3 4
说明
• 对于60% 的数据&＃xff0c; 1 <&＃61; N . M <&＃61; 10^3 &＃xff1b;
• 对于100% 的数据&＃xff0c;1 <&＃61; N , M <&＃61; 10^5。
今晚看偶然LXL dalao 在努力钻研着这个题&＃xff0c;去和他研究了一会于是乎对这题产生了兴趣。
问了一圈人好像都是40,50,60分&＃xff0c;还被个人嘲讽了&＃xff08;原因是我没做&＃xff09;。
独自静静回到电脑前&＃xff0c;开始肆无忌惮的敲着代码&＃xff0c;看着好像不是挺难。
貌似不太对哦&＃xff0c;好像不是辣么简单。
要不先打个60分玩玩&＃xff08;额...60分好像不会写&＃xff09;&＃xff0c;要不....打正解&＃xff1f;&＃xff08;.....&＃xff09;
#include
#include
#include
using namespace std;
const int maxn&＃61;100011;
int tot,head[maxn];
int n,m,x,y;
int f[maxn];
struct ahah{int nxt,to;
}edge[maxn];
void add(int x,int y) // 灵光一闪&＃xff0c;反向建边。
{edge[&＃43;&＃43;tot].nxt&＃61;head[y];edge[tot].to&＃61;x;head[y]&＃61;tot;
}
void dfs(int x,int d) // dfs遍历能跑到哪&＃xff1f;
{ // d记录初始点(是有哪个点开始跑) if(!f[x])f[x]&＃61;x;for(int i&＃61;head[x];i;i&＃61;edge[i].nxt){if(!f[edge[i].to])f[edge[i].to]&＃61;d,dfs(edge[i].to,d);}
}
int main()
{scanf("%d%d",&n,&m);for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;)scanf("%d%d",&x,&y),add(x,y);for(int i&＃61;n;i>&＃61;1;i--)dfs(i,i); // 要找跑到最大的点&＃xff0c;所以反响跑最优。 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)printf("%d ",f[i]);
}
![扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]](https://img.php1.cn/3c972/245b5/42f/19446f78530d3747.jpeg)
京公网安备 11010802041100号