标准每个点都搜一次的 60 分代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n, m;
vector<int> e[MAXN + 5];
bool vis[MAXN + 5];
int dfs(int u)
{
    int res = u;
    vis[u] = true;
    for (int v : e[u])
    {
        if (!vis[v])
        {
            res = max(res, dfs(v));
        }
    }
    vis[u] = false;
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
    }
    for (int i = 1; i <= n; i++)
        cout << dfs(i) << " ";

    return 0;
}

标准做法

从大到小枚举每个点，把每个目前还不知道答案的点都标记为答案为当前这个数。

下面是深搜的做法，广搜的做法完全一致，只有标记的部分从深搜标记改为广搜标记即可。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n, m;
vector<int> e[MAXN + 5];
int ans[MAXN + 5];
void dfs(int u, int x)
{
    ans[u] = x;
    for (int v : e[u])
        if (ans[v] == 0)
            dfs(v, x);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        e[v].push_back(u); // 反向边
    }
    for (int i = n; i >= 1; i--)
        if (ans[i] == 0)
            dfs(i, i);
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    return 0;
}