2017第八届蓝桥杯决赛(C++ B组)4.发现环

描述

小明的实验室有N台电脑,编号1~N。原本这N台电脑之间有N-1条数据链接相连,恰好构成一个树形网络。在树形网络上,任意两台电脑之间有唯一的路径相连。 不过在最近一次维护网络时,管理员误操作使得某两台电脑之间增加了一条数据链接,于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径,使得这些电脑上的数据传输出现了BUG。 为了恢复正常传输。小明需要找到所有在环路上的电脑,你能帮助他吗?

输入 第一行包含一个整数N。 以下N行每行两个整数a和b,表示a和b之间有一条数据链接相连。 对于30%的数据,1 <= N <= 1000 对于100%的数据, 1 <= N <= 100000, 1 <= a, b <= N 输入保证合法。

输出 按从小到大的顺序输出在环路上的电脑的编号,中间由一个空格分隔。 样例输入: 5 1 2 3 1 2 4 2 5 5 3 样例输出: 1 2 3 5

思路

DFS搜索,直到找到一条可以返回起点的路径为止。 由于是无向图,需要注意一下 如果所有点都遍历了还是没找到那就直接返回,即:

    if (walk.size() == n) {
        return;
    }

而且如果发现环那么那个环上每个点出发都会输出一次,而题目只要求输出一次,所以还要保存一下当前找到的环,对应代码:

if (std::find(found.begin(), found.end(), walk) == found.end()) {
            found.push_back(walk);
            for (int i = 0; i < walk.size(); i++) {
                std::cout << walk[i] << " ";
            }
            std::cout << "\n";
        }
        return;

然后就是日常的DFS遍历了。

源码

#include <iostream>
#include <map>
#include <algorithm>
#include <vector>

int n = 0;
std::vector<std::vector<int>> found;

std::multimap<int, int> edge;
void dfs(std::vector<int> walk, int start, int current) {
    if (start == current) {
        std::sort(walk.begin(), walk.end());
        if (std::find(found.begin(), found.end(), walk) == found.end()) {
            found.push_back(walk);
            for (int i = 0; i < walk.size(); i++) {
                std::cout << walk[i] << " ";
            }
            std::cout << "\n";
        }
        return;
    }
    if (walk.size() == n) {
        return;
    }

    auto begin = edge.lower_bound(current);
    auto end = edge.upper_bound(current);
    while (begin != end) {
        int node = begin->second;
        if (walk[walk.size() - 1] != node) {
            // If we haven't visited this node
            walk.push_back(current);
            dfs(walk, start, node);
            walk.pop_back();
        }
        ++begin;
    }
}

int main() {
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b;
        std::cin >> a >> b;
        edge.insert({ a,b });
        edge.insert({ b,a });
    }
    for (auto b = edge.begin(); b != edge.end(); ++b) {
        std::vector<int> walk;
        walk.push_back(b->first);
        dfs(walk, b->first, b->second);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CreateAMind

开源|MultiNet模型解决Kitti数据集自动驾驶中的道路分割、车辆检测和街道分类(附源代码)

MultiNet能够同时完成道路分割、汽车检测和道路分类的任务。MultiNet模型的实时存档速度和分割性能都处于最先进水平。详细的模型描述请查阅我们的论文。

2253
来自专栏小巫技术博客

A008-drawable资源

关于drawable资源笔者之前有写过两篇文章: Android-自定义图像资源的使用(1) Android-自定义图像资源的使用(2) 这里笔者就不做过多的赘...

802
来自专栏小詹同学

人脸识别(三)——源码放送

人脸识别相关的基本原理和流程,以及各个步骤的介绍和代码前两篇都有介绍,其实可以通过前两篇自行整合出完整的人脸识别源码,并且适当修改可以实现MFC程...

5378
来自专栏专知

Tensorflow Eager Execution入门指南

本文介绍了最新版的Tensorflow 1.7的功能及其使用方法,重点介绍其中最有趣的功能之一eager_execution,它许用户在不创建静态图的情况下运行...

53412
来自专栏人工智能LeadAI

Tensorboard入门 | TensorFlow深度学习笔记

Tensorboard是TensorFlow自带的一个强大的可视化工具 01 功 能 这是TensorFlow在MNIST实验数据上得到Tensorboard...

3975
来自专栏ATYUN订阅号

防止在训练模型时信息丢失 用于TensorFlow、Keras和PyTorch的检查点教程

如果你玩过电子游戏,你就会明白为什么检查点(chekpoint)是有用的了。举个例子,有时候你会在一个大Boss的城堡前把你的游戏的当前进度保存起来——以防进入...

5615
来自专栏深度学习那些事儿

pytorch中读取模型权重数据、保存数据方法总结

pytorch中保存数据策略在长时间的深度训练中有很大的作用,我们可以通过保存训练好的权重,然后等到下次使用的时候再取出来。另外我们也可以通过迁移学习使用别人训...

5.1K8
来自专栏磐创AI技术团队的专栏

Tensorboard 详解(上篇)

2083
来自专栏人工智能LeadAI

逻辑回归 | TensorFlow深度学习笔记

课程目标:学习简单的数据展示,训练一个Logistics Classifier,熟悉以后要使用的数据 Install Ipython NoteBook 可以参考...

3117
来自专栏AI2ML人工智能to机器学习

TF Boy 之初筵 - 分布十三式

我们在 " 机器学习平台的优化器 (平台篇、优化篇)" 里面提到TensorFlow (TF) 速度的成为深度学习的武林第一大帮。 博士好友清华,在这方面也颇有...

712

扫码关注云+社区