2024/1/24 图的基本应用

本文介绍: 思路：这道题就是先建图，然后dfs深搜输出，bfs宽搜输出就行了。思路：这道题反向建图，然后依次遍历，输出答案就可以了。

查找文献

P5318 【深基18.例3】查找文献 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：这道题就是先建图，然后dfs深搜输出，bfs宽搜输出就行了

完整代码：

#include <bits/stdc++.h>
#define int long long
const int N = 1e6 + 10;
std::vector<std::vector<int>> g(N);//建一个二维数组，输入x,y 把y放进x里面
int n, m;
bool vis[N]{};
void dfs(int cur) {
    std::cout << cur << " ";//到了哪一层就输出哪一层
    vis[cur] = true;
    for (int i = 0; i < (int) g[cur].size(); i++)//遍历这一个节点连接的所有文献
    {
        if (vis[g[cur][i]] == false)//如果还没有输出
            dfs(g[cur][i]);//继续搜索
    }
}
void bfs() {
    memset(vis, 0, sizeof(vis));//清空上一层dfs的
    std::queue<int> q;//建一个队列
    q.push(1);//因为是从1号节点开始所以把1放进去
    vis[1] = true;//标记，后面的就不能走这条路了
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        std::cout << cur << " ";
        for (int i = 0; i < (int) g[cur].size(); i++) {
            if (vis[g[cur][i]] == false) {
                q.push(g[cur][i]);
                vis[g[cur][i]] = true;
            }
        }
    }
}
signed main() {
    std::cin >> n >> m;//输入数据
    for (int i = 1; i <= m; i++) {
        int x, y;
        std::cin >> x >> y;
        g[x].push_back(y);//把y放进x里面
    }
    for (int i = 1; i <= n; i++) {
        std::sort(g[i].begin(), g[i].end());//一个节点可能连了多个文献，所以对这一个节点的文献进行排序
    }
    dfs(1);//从1号点开始搜索
    std::cout << "n";
    bfs();
    return 0;
}

图的遍历

P3916 图的遍历 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：这道题反向建图，然后依次遍历，输出答案就可以了

完整代码：

#include <bits/stdc++.h>
#define int long long
const int N = 1e5 + 10;
std::vector<std::vector<int>> g(N);
int n, m;
int a[N];
void dfs(int cur,int d)
{
    if(a[cur]!=0)
        return;
    a[cur]=d;
    for(int i = 0;i < g[cur].size();i ++)
    {
        dfs(g[cur][i],d);
    }
}
signed main() {
    std::cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        std::cin >> x >> y;
        g[y].push_back(x);
    }
    for (int i = n; i >= 1; i--) {
        dfs(i,i);
    }
    for(int i = 1;i <= n;i ++)
    {
        std::cout<<a[i]<<" ";
    }
    return 0;
}

原文地址:https://blog.csdn.net/weixin_73793099/article/details/135826587

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。

如若转载，请注明出处：http://www.7code.cn/show_61421.html

如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。