題目描述

某山區(qū)有高高低低的 n 個(gè)山峰，根據(jù)海拔高度的不同，這些山峰由低到高進(jìn)行了 1 到 n 編號(hào)。 有 m 條只能單向通行的羊腸小道連接這些山峰?，F(xiàn)在，這里要舉行一場(chǎng)跳傘登山賽，選手們傘降到 某山峰后，再通過山間小道向?qū)儆谧约旱淖罡叻暹M(jìn)軍。 小明也參加了這次比賽，你能否告訴他，從任意一座山峰出發(fā)所能到達(dá)的最高峰編號(hào)是多少？

輸入格式

輸入共 m+1 行。
第 1 行為 2 個(gè)整數(shù) n、m，用一個(gè)空格隔開，表示山峰總數(shù)和道路總數(shù)。
接下來 m 行，每行 2 個(gè)整數(shù)，用一個(gè)空格隔開，表示一條道路的起點(diǎn)和終點(diǎn)山峰編號(hào)。

輸出格式

輸出共 1 行，n 個(gè)整數(shù)，用一個(gè)空格隔開，表示每座山峰所能到達(dá)的最高峰的編號(hào)。

輸入/輸出例子1

輸入：
4 3
1 2
2 4
4 3
輸出：
4 4 3 4
樣例解釋
【數(shù)據(jù)范圍】
60%的數(shù)據(jù)滿足：1≤m,n≤103；
100%的數(shù)據(jù)滿足：1≤m,n≤105。

代碼

#include<iostream>
#include<cstdio>
#include<vector>
#include <cstring>
using namespace std;
static std::vector<int> edge[100005];
static bool visit[100005];
static int f[100005], n, m, s, e;
static void dfs(int& val, int sta)
{
    visit[sta] = true;
    for (int i = 0; i < edge[sta].size(); i++)
        if (!visit[edge[sta][i]])
        {
            if (f[edge[sta][i]] > val)
            {
                val = f[edge[sta][i]];
            }
            dfs(val, edge[sta][i]);
        }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &s, &e);
        edge[s].push_back(e);
    }
    for (int i = 1; i <= n; i++)
        f[i] = i;
    for (int i =1 ; i <=n ; i++)
    {
        dfs(f[i], i);
        memset(visit,0,sizeof(visit));
    }
    for (int i = 1; i <= n; i++) printf("%d ", f[i]);
    return 0;
}