传送门

思路

对于有向图遍历选择目标结点（有汇聚，即多个点的目标结点为同一个点）时，如果对每个点都进行深搜时间复杂度过高，可以考虑反向建边。

代码

#include
#include
using namespace std;
const int MAX = 1e5 + 10;
vector Find[MAX];
int Array[MAX];
void DFS(int number,int res) {
    Array[number] = res;
    for (int i = 0; i < Find[number].size(); i++)
        if (!Array[Find[number][i]])
            DFS(Find[number][i], res);
    return;
}
int main(void)
{
    int N = 0, M = 0, from = 0, to = 0;
    cin >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        cin >> from >> to;
        Find[to].push_back(from);
    }
    for (int i = N; i >= 1; i--)
        if (!Array[i])
            DFS(i, i);
    for (int i = 1; i <= N; i++)
        cout << Array[i] << " ";
    return 0;
}