洛谷 P3916 - 图的遍历（反向建边）

---

题目描述

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

输入格式

第 $1$ 行 $2$ 个整数 $N,M$，表示点数和边数。

接下来 $M$ 行，每行 $2$ 个整数 $U_i,V_i$，表示边 $(U_i,V_i)$。点用 $1,2,\dots ,N$ 编号。

输出格式

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

样例

样例输入 #1

4 3
1 2
2 4
4 3
1
2
3
4

样例输出 #1

4 4 3 4
1

提示

• 对于 $60\%$ 的数据，$1\le N,M\le 10^3$。
• 对于 $100\%$ 的数据，$1\le N,M\le 10^5$。

---

• 注意到本题的数据量为$10^5$，所以果断考虑链式前向星存图。一开始的思路是将每个点dfs一遍，然后在dfs的过程中将能遇到的结点编号取一个max，再接着输出就可以了。

没想到居然TLE了两个测试样例，看来这题也不简单啊>_>。

• 然后也是采取了某大佬的思路，即反向建边＋dfs，具体就是在建边时反着建，如样例中a —> b则add(b, a)，这样做是为了能够让b结点返回来找到a，然后最核心的一步来了：按结点编号从大到小的顺序挨着深搜一遍，将每个dfs起点标记成它遍历路径上的遇到的结点i的A[i]。
• 定义一个st[]数组表示st[i]：结点i的A[i]找到了
• 假设现在的结点集合为(4, 3, 2, 1)，从4开始遍历，假如4能到达的点有1、2，那么1、2的A[1]、A[2]就等于4，因为即使3、2. . .这些点可以到达1、2，那它们也不可能成为那个A[i]，因为有4更大，所以此时可以给st[1]、st[2]做上记号true，以后遍历时再遇到时便可直接跳过，所以从大到小来枚举各点的优势就在这：提前确定好各点的最大可达点，并在后面点的遍历过程中跳过。

C++代码

#include 
#include 
#include 
using namespace std;

const int N = 1e5 + 10;

int e[N], ne[N], h[N], A[N];
bool st[N];
int n, m, idx = 0;
int ans;

void add(int a, int b){         //链式前向星存图
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void dfs(int u){
    st[u] = true;
    A[u] = ans;

    for(int i = h[u];i != -1;i = ne[i]){
        int j = e[i];    
        if(!st[j])          dfs(j);
    }
}

int main(){
    ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m --){
        int u, v;
        cin >> u >> v;
        add(v, u);
    }

    for(int i = n;i >= 1;i --){
        if(!st[i]){
            ans = i;
            dfs(i);
        }
    }

    for(int i = 1;i <= n;i ++)      cout << A[i] << " ";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48