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

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

成品课程

陈远龙老师主讲 & 答疑

未购买 · 可先试学5节课

课程目录展开/折叠

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

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

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

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

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

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

本节课讲解到的源代码

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

1. t4 - C1116 - 图的遍历 - 90分解法 

#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]; // a[1] 1 => maxid

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

// 1. 杩斿洖鍊?
int dfs(int u)
{
    // cout << u << ' ';
    vis[u] = true;
    int mxid = u;
    for (int i = 0; i < g[u].size(); i ++)
    {
        int v = g[u][i];
        // v mxid
        // mxid = max(mxid, v);
        if (!vis[v])
        {
            mxid = max(mxid, dfs(v));
        }
    }

    return mxid;
}

void dfs2()
{
    for (int u = 1; u <= n; u ++)
    {
        memset(vis, 0x00, sizeof(vis));
        ans[u] = dfs(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);
    }

    // dfs(1);

    dfs2();

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

    return 0;
}
2. t4-2 - C1116 - 图的遍历 - 90分解法 

#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]; // a[1] 1 => maxid

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

// 1. 杩斿洖鍊?
void dfs(int u, int from)
{
    vis[u] = true;
    ans[from] = max(u, ans[from]);
    for (int i = 0; i < g[u].size(); i ++)
    {
        int v = g[u][i];

        if (!vis[v]) dfs(v, from);
    }
}

void dfs2()
{
    for (int u = 1; u <= n; u ++)
    {
        memset(vis, 0x00, sizeof(vis));
        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);
    }

    // dfs(1);

    dfs2();

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

    return 0;
}

本节课课后练习题

  1. C1116 - 图的遍历

本节课答疑

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

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

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

目录