Hrbust ACM练习 2024级第11周题单 题解分享 (A-B)

相关文章链接

• 算法题练习 题解分享 文章汇总

前言

题单链接：2024第11周题单 图论基础 – Virtual Judge

A 题

原题链接：P5318 【深基18.例3】查找文献 – 洛谷

Cpp Code

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<bool> vis;
vector<int> max_node;
vector<vector<int>> adj;

void dfs(int u) {
    if (vis[u]) {
        return;
    }

    vis[u] = true;
    cout << u << " ";
    for (int i = 0; i < (int)adj[u].size(); ++i) {
        dfs(adj[u][i]);
    }
    return;
}

// 另一种 dfs 实现
// void dfs(int u) {
//     vis[u] = true;
//     cout << u << " ";
//     for (int i = 0; i < (int)adj[u].size(); ++i) {
//         int next_node = adj[u][i];
//         if (!vis[next_node]) {
//             dfs(next_node);
//         }
//     }
//     return;
// }

void bfs(int u) {
    queue<int> q;

    q.push(u);
    vis[u] = true;
    cout << u << " ";

    while (!q.empty()) {
        u = q.front();
        q.pop();
        for (int i = 0; i < (int)adj[u].size(); ++i) {
            if (!vis[adj[u][i]]) {
                q.push(adj[u][i]);
                vis[adj[u][i]] = true;
                cout << adj[u][i] << " ";
            }
        }
    }
}

int main() {
    cin >> n >> m;

    adj.resize(n + 1);

    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    for (int i = 1; i <= n; i++) {
        sort(adj[i].begin(), adj[i].end());
    }

    vis.assign(n + 1, false);
    for (int i = 1; i <= 2; i++) {
        dfs(i);
    }

    cout << '\n';

    vis.assign(n + 1, false);
    bfs(1);

    return 0;
}

B 题

原题链接：P3916 图的遍历 – 洛谷

Cpp Code

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<bool> vis;
vector<int> max_node;
vector<vector<int>> adj;

void dfs(int u, int start_node) {
    if (vis[u]) {  // 要是访问过，一定是被比较大的 start_node 访问的
        return;
    }
    vis[u] = true;
    max_node[u] = start_node;
    for (int i = 0; i < (int)adj[u].size(); ++i) {
        dfs(adj[u][i], start_node);
    }
    return;
}

int main() {
    cin >> n >> m;

    vis.assign(n + 1, false);
    adj.resize(n + 1);
    max_node.resize(n + 1);

    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[v].push_back(u);
    }

    for (int i = n; i >= 1; i--) {
        dfs(i, i);
    }
    for (int i = 1; i <= n; ++i) {
        cout << max_node[i] << " ";
    }

    return 0;
}