李依霄
(李依霄)
1
时间：1s 空间：512M
题目描述：
小埋最近在学习有向图的遍历相关知识，小埋学习过图的遍历的相关方法，可以使用dfs或者bfs来遍历整个有向图，但是小埋发现这个问题有一些不一样，这个图的遍历是问你当前点能够到达的点的最大编号，小埋希望你能帮她解决这个问题。
输入格式：
第一行两个整数一个n一个m，n代表有向图中有n个点，m代表有向图中有m条有向边。
接下来是m条边。
输出格式：
输出每个点能够到达的最大编号
样例1输入：
4 3
1 2
1 3
2 3
样例1输出：
3 3 3 4
数据范围：
1<=n,m<=100000
墓前TLE10分
tyx
(༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)
2
我的思路：如果你要正序的话那就用记忆化。（我没写）
但如果你反向建边的话那你就倒序遍历：
for(int i=n;i>=1;i--)dfs(i,i);
dfs函数的话，因为我们是从大往小搜，那么只要一搜到，那就是最大的：
void dfs(int x,int k){//k传当前出发结点的值
if(vis[x]) return;
vis[x]=k;
for(auto i:v[x])dfs(i,k);
}
1 个赞