Skip to content

14290: 【原4290】图的遍历hard

题目

题目描述

author: Guo Linsong 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4290

Description

此题是上一道题目的数据加强版。

给定$n$个点,$m$条边的有向图,对于每个点$v$,求$f(v)$表示从点$v$出发能到达的编号最大的点(包括自己在内)。

$n,m\leq 10^5$

Input Format

第一行有$2$个整数$n$,$m$。 接下来$m$行,每行2个整数$u_i,v_i$,表示$u_i$到$v_i$有一条边。 点用$1,2,\cdots,n$编号。

Output Format

$n$个整数$f(1),f(2),\cdots,f(n)$.

Sample Input 1

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

Sample Output 1

3 5 3 4 5

Sample Input 2

5 0

Sample Output 2

1 2 3 4 5

Note

此题不需要Tarjan算法、拓扑排序等其他没有讲过的算法。

zqy2018's solution

/*
    See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu4290.md
*/
#include <cstdio>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m;
int at[100005] = {0}, nxt[100005], to[100005], cnt = 0;
int f[100005] = {0};
bool vis[100005] = {0};
void dfs(int cur){
    vis[cur] = true;
    for (int i = at[cur]; i; i = nxt[i]){
        if (!vis[to[i]])
            f[to[i]] = f[cur], dfs(to[i]);
    }
}
void init(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i){
        int u, v;
        scanf("%d%d", &u, &v);
        to[++cnt] = u, nxt[cnt] = at[v], at[v] = cnt;
    }
}
void solve(){
    for (int i = n; i >= 1; --i){
        if (!vis[i])
            f[i] = i, dfs(i);
    }
    for (int i = 1; i < n; ++i)
        printf("%d ", f[i]);
    printf("%d\n", f[n]);
}
int main(){
    init();
    solve();
    return 0;
}