题目名称（假设）：最大可达节点值

问题描述（假设）：

给定一个有向图，每个节点有一个唯一的编号（1到n），求每个节点能够到达的所有节点中编号最大的那个节点值。

#include<bits/stdc++.h>  
using namespace std;
const int N=1e5+10;
vector<int> G[N]; //vector存图 
int f[N];  
void dfs(int x, int mx) 
{
    if(f[x]) return; //访问过 
    f[x] = mx;
    for(auto y : G[x])//遍历x的邻接节点
    {
        dfs(y, max(y, mx));
    }
}
  
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=1, x, y; i<=m; i++)
    {
        scanf("%d%d", &x, &y);
        G[y].push_back(x); //反向建边，将y指向x的边转为x的邻接边
    }
    memset(f, 0, sizeof(f)); //初始化f数组
    for(int i=n; i>=1; i--) //从编号最大的节点开始遍历
        dfs(i, i); //初始时，节点i的最大可达节点为自身
    for(int i=1; i<=n; i++) 
        printf("%d ", f[i]); //输出每个节点的最大可达节点值
    printf("\n");
    return 0;
}

解题思路（假设）：

1. 反向建边：将原图中从x到y的边（x→y）转化为y到x的边（y←x），即G[y].push_back(x)，方便后续处理节点间的可达关系。
2. 深度优先搜索（DFS）：从编号最大的节点n开始，依次向下遍历所有节点。每个节点x在DFS中会将其邻接节点y的最大可达节点值更新为max(y, 当前节点x的最大可达节点值)，确保每个节点只被访问一次（通过f数组标记已访问）。
3. 结果输出：遍历完成后，f数组中存储的即为每个节点的最大可达节点值。

使用说明：

• 时间复杂度O(n+m)，适用于n≤1e5的规模。
• 空间复杂度O(n+m)，主要用于存储图和递归栈。

#include<bits/stdc++.h>  
using namespace std;
const int N=1e5+10;
vector<int> G[N]; //vector存图 
int f[N];  
void dfs(int x,int mx) 
{
    if(f[x]) return; //访问过 
    f[x]=mx;
    for(auto y:G[x])//for(int i=0; i<G[x].size(); i++){ int y=G[x][i];
    {
        dfs(y,max(y,mx));
    }
}
  
int main()
{
    int n,m;scanf("%d%d", &n, &m);
    for(int i=1,x,y; i<=m; i++)
    {
        scanf("%d%d", &x, &y);
        G[y].push_back(x); //反向建边 
    }
    memset(f,0,sizeof(f)); 
    for(int i=n;i>=1;i--)dfs(i,i); 
    for(int i=1; i<=n; i++) printf("%d ", f[i]);
    printf("\n");
    return 0;
}