题目描述

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

输入格式

第 $1$ 行，$2$ 个整数 $N, M$。

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

输出格式

$N$ 个整数 $A(1), A(2), \cdots, A(N)$。

输入输出样例

输入 #1

4 3
1 2
2 4
4 3

输出 #1

4 4 3 4

说明/提示

• 对于 $60%$ 的数据，$1 \le N . M \le 10^3$；

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

题解

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010;
int f[N];
int n, m;
vector<int> g[N];

void dfs(int s, int t) {
    if(f[s]) return;
    f[s] = t;
    for(int i = 0; i < g[s].size(); i++)
        dfs(g[s][i], t);
}

int main() {
    cin >> n >> m;
    int a, b;
    for(int i = 0; i < m; i++) {
        cin >> a >> b;
        g[b].push_back(a);
    }
    for(int i = n; i; i--) dfs(i, i);
    for(int i = 1; i <= n; i++) cout << f[i] << " ";
    puts("");
    return 0;
}