洛谷P3916 图的遍历

题目传送门：https://www.luogu.com.cn/problem/P3916

解法一：DFS

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> pii;
constexpr int N = 1e5 + 5, M = 1e5 + 5;
int ver[M], nxt[M], head[N], tot, vis[N], d[N];
void add(int x, int y) {
    ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}
void dfs(int x, int val) {
    if (vis[x]) return;
    vis[x] = 1;
    d[x] = val;
    for (int i = head[x]; i ; i = nxt[i]) {
        int y = ver[i];
        dfs(y, val);
    }
}
void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        add(y, x);
    }
    for (int i = n; i >= 1; --i) {
        dfs(i, i);
    }
    for (int i = 1; i <= n; ++i) {
        cout << d[i] << ' ';
    }
}

int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

解法二：BFS

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> pii;
mt19937_64 rng(random_device{}());
const int N = 1e5 + 10, M = 1e5 + 10;
int ver[M], nxt[M], head[N], tot;
int d[N];
bool vis[N];
void add(int x, int y) {
    ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}
void bfs(int st) {
    queue<int> q;
    q.push(st);
    vis[st] = 1;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (vis[y]) continue;
            vis[y] = 1;
            d[y] = d[x];
            q.push(y);
        }
    }
}
void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        add(y, x); // reverse
    }
    iota(d, d+1+N, 0);
    for (int i = n; i >= 1; --i) {
        bfs(i);
    }
    for (int i = 1; i <= n; ++i) {
        cout << d[i] << ' ';
    }
}
int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}