Loading... [题目链接](https://www.luogu.org/problemnew/show/P3916 "题目链接") <!--more--> * * * 又是一道神奇的题目，题目问从每个点能到达的编号最大的点，相当于一到多，这样可以建反向边，然后跑dfs。 每个点跑一遍dfs，从n到1循环。 代码： ```cpp #include<bits/stdc++.h> using namespace std; int n,m,ans[100009]; struct Edge{ int to,nxt; }e[100009]; int head[100009],tot; void add(int x,int y){ e[++tot].to=y; e[tot].nxt=head[x]; head[x]=tot; } void dfs(int x,int fa){ if(ans[x]!=0) return; ans[x]=fa; for(int i=head[x];i;i=e[i].nxt){ int y=e[i].to; if(ans[y]==0) dfs(y,fa); } } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int x,y; cin>>x>>y; add(y,x); } for(int i=n;i>=1;i--){ dfs(i,i); } for(int i=1;i<=n;i++){ cout<<ans[i]<<" "; } return 0; } ``` Last modification：March 14, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏