首页
课程
真题 题单
题库
书单 OI导航 直播 购买课程
修改密码

【2024课程】CSP-J/S复赛备考精讲课程

成品课程

陈远龙老师主讲 & 答疑

未购买 · 可先试学5节课

课程目录展开/折叠

第4课 CSP-J/S复赛备考精讲

视频 PPT&板书 讲课代码 课后练习
播放快捷键

播放/暂停：空格（或鼠标单击）      全屏：F（或鼠标双击）      退出全屏：Esc

快进10 / 30 / 60秒：方向键→ / Ctrl + 方向键→ / Shift + 方向键→

快退10 / 30 / 60秒：方向键← / Ctrl + 方向键← / Shift + 方向键←

本节课讲解配套PPT&板书：

本节课讲解到的源代码

源代码下载：第4课 CSP-J/S复赛备考精讲-源代码下载

1. t4 - C1116 - 图的遍历 - 反向建图 - dfs - vector邻接表 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
vector<int> g[N];
bool vis[N];
int n, m;
int ans[N];

void addEdge(int u, int v)
{
    g[u].push_back(v);
}

void dfs(int u, int fa)
{
    // cout << u << ' ';
    vis[u] = true;
    ans[u] = fa; // if (ans[u] == 0) ans[u] = fa
    for (int i = 0; i < g[u].size(); i ++)
    {
        int v = g[u][i];
        if (!vis[v]) dfs(v, fa);
    }
}

void dfs2()
{
    for (int u = n; u >= 1; u --)
    {
        if (!vis[u]) dfs(u, u);
    }
}

int main()
{
    // freopen("t4.in", "r", stdin);
    // freopen("t4.out", "w", stdout);

    const char endl = '\n';
    ios::sync_with_stdio(false);
    cin.tie(0);

    // int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i ++)
    {
        int u, v;
        cin >> u >> v;
        // addEdge(u, v);
        addEdge(v, u); // 反向建图
    }

    dfs2();

    for (int i = 1; i <= n; i ++)
        cout << ans[i] << ' ';

    return 0;
}
2. t4-2 - C1116 - 图的遍历 - dfs - 链式前向星邻接表 

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
const int M = 1e5 + 5;
struct Edge {
    int to;
    // int w;
    int nxt;
};

Edge e[M];
int cnt = 1;
int head[N];
bool vis[N];
int ans[N];

int n, m;

void addEdge(int u, int v)
{
    int cur = cnt ++;
    e[cur].to = v;

    // head[u] -> cur
    e[cur].nxt = head[u];
    head[u] = cur;
}

void dfs(int u, int fa)
{
    ans[u] = fa;
    vis[u] = true;

    for (int i = head[u]; i != 0; i = e[i].nxt)
    {
        int v = e[i].to;
        if (!vis[v]) dfs(v, fa);
    }
}

void dfs2()
{
    for (int u = n; u >= 1; u --)
    {
        if (!vis[u]) dfs(u, u);
    }
}

int main()
{
    // freopen("t4.in", "r", stdin);
    // freopen("t4.out", "w", stdout);

    const char endl = '\n';
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    for (int i = 0; i < m; i ++)
    {
        int u, v;
        cin >> u >> v;
        // addEdge(u, v);
        addEdge(v, u); // 反向建图
    }

    dfs2();

    for (int i = 1; i <= n; i ++)
        cout << ans[i] << ' ';

    return 0;
}
2. t4-3 - C1116 - 图的遍历 - bfs - 链式前向星邻接表 

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
const int M = 1e5 + 5;
struct Edge {
    int to;
    // int w;
    int nxt;
};

Edge e[M];
int cnt = 1;
int head[N];
bool inq[N];
int ans[N];

int n, m;

void addEdge(int u, int v)
{
    int cur = cnt ++;
    e[cur].to = v;

    // head[u] -> cur
    e[cur].nxt = head[u];
    head[u] = cur;
}

void bfs(int u)
{
    queue<int> q;
    q.push(u);
    ans[u] = u;
    inq[u] = true;

    while (!q.empty())
    {
        int u1 = q.front();
        q.pop();
        // cout << u1 << ' ';

        for (int i = head[u1]; i != 0; i = e[i].nxt)
        {
            int v = e[i].to;
            if (!inq[v])
            {
                q.push(v);
                ans[v] = u;
                inq[v] = true;
            }
        }

    }
}

void bfs2()
{
    for (int u = n; u >= 1; u --)
    {
        if (!inq[u]) bfs(u);
    }
}

int main()
{
    // freopen("t4.in", "r", stdin);
    // freopen("t4.out", "w", stdout);

    const char endl = '\n';
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    for (int i = 0; i < m; i ++)
    {
        int u, v;
        cin >> u >> v;
        // addEdge(u, v);
        addEdge(v, u); // 反向建图
    }

    bfs2();

    for (int i = 1; i <= n; i ++)
        cout << ans[i] << ' ';

    return 0;
}

本节课课后练习题

  1. C1116 - 图的遍历

本节课答疑

建议大家有问题先通过AI答疑（比如：DeepSeek 等），AI时代需要学会使用AI辅助学习

陈远龙老师视频讲解：如何使用DeepSeek进行答疑？

通过AI未能获得满意解答的，可以联系陈远龙老师答疑

目录