【题目描述】
给出 N 个点，M 条边的有向图，对于每个点 v，求 A(v) 表示从点 v 出发，能到达的编号最大的点。
【输入】
第 1 行 2 个整数 N,M，表示点数和边数。
接下来 M 行，每行 2 个整数 Ui,Vi，表示边 (Ui,Vi)。点用 1,2,…,N 编号。
【输出】
一行 N 个整数 A(1),A(2),…,A(N)。
【输入样例】
4 3 1 2 2 4 4 3【输出样例】
4 4 3 4【提示】
对于 60% 的数据，1≤N,M≤2000。
对于 100% 的数据，1≤N,M≤105。
1. 问题分析
题目要求对于图中的每个点i，求出它能到达的所有点中，编号最大的那个点。
最直观的暴力做法（我下面代码中第一个做法）是：
对1--N的每一个点分别进行一次 DFS。
时间复杂度：O(N*(N+M))。
结果：当 N=10^5时，计算量达到百亿级，必定TLE。
痛点：正向搜索时，为了防止死循环，每轮都要清空
vis数组，导致大量重复访问相同的路径。
2. 优化思路：正难则反
如果我们正向寻找“u能去哪”，不知道终点是谁，必须走到底。
不妨换个角度：看“编号最大的点”能反向走到谁。
如果在反向图中，点Target能走到点 u，那么在原图中u一定能走到Target。
3. 算法核心策略
利用反向建图配合贪心策略，只需遍历一次图即可求解。
反向建图：
对于输入的每条边 u -> v，我们建立反向边 v -> u。
从大到小枚举（贪心）：
我们从编号最大的点N开始，倒序遍历到1。
DFS：
当我们在反向图中从点i出发搜索时，凡是能被i访问到的点（且之前未被访问过），它们在原图中能到达的编号最大的点就是i。
关键点：因为我们要找最大值，且外层循环是从大到小进行的。所以，一个点第一次被访问时，标记它的那个起点i一定是它能接触到的最大编号。
剪枝：既然第一次访问就是最大值，那么后续如果再遇到已访问的点，直接跳过，无需重复计算。
通过这种方式，每个点和每条边只会被访问一次，时间复杂度降为O(N+M)。
4. 完整代码
/* //这道题正向建图会超时 #include <iostream> using namespace std; int h[100010];//头指针数组 int vtex[100010];//存放节点 int nxt[100010]; int idx; int cnt;//从自身出发能到达的编号最大的点 int vis[100010]; int n,m; void dfs(int k){ cnt=max(cnt,k); if(cnt==n) return;//当能到达的点为n时，就不可能更大了 int p=h[k]; while(p!=-1){ if(vis[vtex[p]]==0){ vis[vtex[p]]=1; dfs(vtex[p]); } p=nxt[p]; } } void addedge(int x,int y){ vtex[idx]=y; nxt[idx]=h[x]; h[x]=idx++; } int main(){ ios::sync_with_stdio(false); cin.tie(0); scanf("%d%d",&n,&m); //因为点数是10^5量级，所以我们选用邻接表形式存图 memset(h,-1,sizeof(h));//初始化h数组 for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); addedge(u,v); } //接下来输出 for(int i=1;i<=n;i++){//挨个点找能到达的编号最大的点 memset(vis,0,sizeof(vis));//每轮要初始化vis数组 cnt=i;//从点i出发能到达的最大的点，初始为自身 vis[i]=1;//标记这个点已经走过，不再次走 dfs(i);//找从自身出发能到达的最大的点 printf("%d ",cnt); } return 0; } */ //所以这道题我们需要反向建图,反向建图 我们从最大点i去递归，然后他能到达的点 //能去到的编号最大的点就是i，且如果i-1已经被i经过了，那i-1就无需计算了，因为 //i能到i-1，i就能到i-1所能去的所有点，但i>i-1,所以肯定以大数为准 #include <iostream> #include <cstring> using namespace std; int h[100010];//头指针 int vtex[100010]; int nxt[100010]; int idx; int ma[100010];//存每个点能到达的最大点 void dfs(int k,int x){//现在递归到k点 起始点x（最大值） int p=h[k]; while(p!=-1){ if(ma[vtex[p]]==0){//如果这个点前面没有别的数经过，那x就是它能到达的最大点 ma[vtex[p]]=x; dfs(vtex[p],x); } p=nxt[p]; } } void addedge(int x,int y){ vtex[idx]=y; nxt[idx]=h[x]; h[x]=idx++; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m; cin>>n>>m; memset(h,-1,sizeof(h));//初始化h数组为每个点都没有头指针 //点数为10^5量级，所以要用邻接表 for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; addedge(v,u);//反向建图 } //接下来从最大点n开始遍历我们从最大点i去递归，然后他能到达的点 //能去到的编号最大的点就是n，且如果n-1能被n经过，n-1就无需计算了，因为 //n能到n-1，i就能到n-1所能去的所有点，但n大于n-1,所以肯定以大数为准，用一个 //数组去存每个点能到的最大值 for(int i=n;i>=1;i--){ if(ma[i]==0){//如果这个数目前没有被更大数经过，就要去递归 dfs(i,i); ma[i]=i;//然后它能去到的最大点就是自身 } //否则就是能被更大数经过，就不需要去搜索这个数的沿途路径了，它能经过的点 //都被更大点赋值了 } //输出 for(int i=1;i<=n;i++){ cout<<ma[i]<<" "; } return 0; }
