图 · 错题仓库

jcs_pp · 2025-03-28 16:12:37 · 个人记录

图的遍历

基本思路：

我们要找每个点能到达的编号最大的点 那么循环从N到1，则每个点i能访问到的结点的A值都是i

每个点访问一次，这个A值就是最优的，因为之后如果再访问到这个结点那么答案肯定没当前大了

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>e[100010];
int v[100010],a[100010];
void f(int x,int zhi)
{
    if(v[x]==1) return;
    v[x]=1;//vis数组不用置0，因为此值一定是最优的 
    a[x]=zhi;
    for(int i=0;i<e[x].size();i++)
    {
        f(e[x][i],zhi);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        e[y].push_back(x);
    }
    for(int i=n;i>0;i--) f(i,i);//循环 
    for(int i=1;i<=n;i++) cout<<a[i]<<' ';
    return 0;
}