[C++] P3916 图的遍历

给出 $N$ 个点，$M$ 条边的有向图，对于每个点 $v$，令 $A(v)$ 表示从点 $v$ 出发，能到达的编号最大的点。现在请求出 $A(1),A(2),\dots,A(N)$ 的值。

输入格式

第 $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

输入 #1

4 3
1 2
2 4
4 3

输出 #1

4 4 3 4

说明/提示

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

题解

#include <iostream>
#include <vector>
using namespace std;

void dfs
(
    vector<size_t> vec[],
    size_t ans[],
    size_t i,
    size_t begin,
    bool visited[]
)
{
    for(auto j : vec[i])
    {
        if(!visited[j])
        {
            visited[j] = true;
            ans[j] = begin;
            dfs(vec, ans, j, begin, visited);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    size_t n, m;
    cin >> n >> m;

    vector<size_t> vec[n];

    while(m--)
    {
        size_t u, v;
        cin >> u >> v;
        vec[v-1].push_back(u-1);
    }

    size_t ans[n];
    bool visited[n] = {false};

    for(size_t i=n; i--; )
    {
        if(!visited[i])
        {
            visited[i] = true;
            ans[i] = i;
            dfs(vec, ans, i, i, visited);
        }
    }

    for(size_t i=0; i<n; i++)
        cout << ans[i]+1 << " ";

    return 0;
}