GHOJ 340 跳伞登山赛

题目描述

        某山区有高高低低的n个山峰，根据海拔高度的不同，  这些山峰由低到高进行了1到n编号。

        有m条只能单向通行的羊肠小道连接这些山峰。现在，这里要举行一场跳伞登山赛，选手们伞降到某山峰后，再通过山间小道向属于自己的最高峰进军。

        小明也参加了这次比赛，你能否告诉他，从任意一座山峰出发所能到达的最高峰编号是多少？

输入输出格式

输入格式

          输入共m+1行。

          第1行为2个整数n、m，用一个空格隔开，表示山峰总数和道路总数。

          接下来m行，每行2个整数，用一个空格隔开，表示一条道路的起点和终点山峰编号。

输出格式

         输出共1行，n个整数，用一个空格隔开，表示每座山峰所能到达的最高峰的编号。

输入输出样例

输入样例

4 3

1 2

2 4

4 3

输出样例

4 4 3 4

说明

数据规模

        60%的数据满足：1≤m,n≤1000。

        100%的数据满足：1≤m,n≤10000。

题解

        从最高峰开始跑记搜即可。

#include <iostream>
#include <set>
#define MAX_N 100001 

using namespace std;

int n;
set<int> s[MAX_N]; 
int ans[MAX_N];
void DFS(int, int);

int main()
{
    int m;
    cin >> n >> m;
    while(m--)
    {
        int prev, next;
        cin >> next >> prev;
        s[prev].insert(next);
    }
    for(register int i = n; i >= 1; i--)
    {
        if(!ans[i]) DFS(i, i); 
    }
    for(register int i = 1; i <= n; i++)
    {
        cout << ans[i];
        if(i < n) cout << ' ';
    }
    return 0;
} 

void DFS(int idx, int val)
{
    ans[idx] = val;
    while(!s[idx].empty())
    {
        int next;
        next = *s[idx].begin();
        s[idx].erase(s[idx].begin());
        if(!ans[next]) DFS(next, val);
    }
    return;
}