P3916 图的遍历

题目描述

给出 NN 个点，MM 条边的有向图，对于每个点 vv，求 A(v)A(v) 表示从点 vv 出发，能到达的编号最大的点。

输入格式

第 11 行 22 个整数 N,MN,M，表示点数和边数。

接下来 MM 行，每行 22 个整数 U_i,V_iUi​,Vi​，表示边 (U_i,V_i)(Ui​,Vi​)。点用 1,2,\dots,N1,2,…,N 编号。

输出格式

一行 NN 个整数 A(1),A(2),\dots,A(N)A(1),A(2),…,A(N)。

输入输出样例

4 3
1 2
2 4
4 3

4 4 3 4

说明/提示

• 对于 60\%60% 的数据，1 \leq N,M \leq 10^31≤N,M≤103。
• 对于 100\%100% 的数据，1 \leq N,M \leq 10^51≤N,M≤105。

这个题我们老师说顺着题目的思路去找答案会很难，所以逆着找，反向建边，从编号最大的点开始找，直到找到终点，那么这个终点能达到的最大的编号就是他了，按照这个思路我们只要先创建邻接表，然后从大到小遍历就好了

#include<iostream>
#include<vector>
using namespace std;
vector<int>p[100001];
int vis[100001];
void dfs(int u,int v) {//u是当前点，v是能到达的最大编号
    if(vis[u])return;//如果标记过，直接返回
    vis[u]=v;//标记当前点
    for(int i=0; i<p[u].size(); i++)//和这个节点联通的所有点继续遍历下去，需要注意的事是vector数组从下标0的地方开始存，所以这里不能i=1，只能是i=0　
        dfs(p[u][i],v);//继续循环，最大点编号不变仍然是v；
}
int main() {
    int n,m;
    cin>>n>>m;
　　//建立邻接表
    for(int i=1; i<=m; i++) {
        int u,v;
        cin>>u>>v;
        p[v].push_back(u);//反向建边
    }
    for(int i=n; i>=1; i--)//从大到小遍历
        dfs(i,i);//从i开始遍历，i为最大点
    for(int i=1; i<=n; i++)//题目要求的从小到大输出
        cout<<vis[i]<<" ";
　　//*潦草结束
    return 0;
}