P3916 图的遍历

Link

Solution

反向建边dfs

Code

#include <memory.h>

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int maxn = 100010;

int vis[maxn], maxd[maxn], cnt = 0;

vector<int> G[maxn];

void dfs(int s, int maxv)
{
    vis[s] = 1;
    cnt++;
    maxd[s] = maxv;
    for (auto i : G[s])
        if (!vis[i]) dfs(i, maxv);
}

int main(int argc, const char* argv[])
{
    int n, m, x, y;
    cin >> n >> m;
    while (m--) {
        cin >> x >> y;
        G[y].push_back(x);
    }
    memset(vis, 0, sizeof(vis));
    for (int i = n; i >= 1; i--) {
        if (!vis[i]) dfs(i, i);
        if (cnt == n) break;
    }
    for (size_t i = 1; i <= n; i++) cout << maxd[i] << " ";
    cout << endl;
    return 0;
}