[C++] P3916 图的遍历

发表于 更新于 分类于

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

输入格式

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

接下来 M 行，每行 2 个整数 Ui, Vi，表示边 (Ui, Vi)。点用 1, 2, …, N 编号。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

1
4 4 3 4

说明/提示

  • 对于 60% 的数据，1 ≤ N, M ≤ 103。
  • 对于 100% 的数据，1 ≤ N, M ≤ 105。

题解

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
49
50
51
52
53
54
55
56
57
58
59
60
#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;
}