蓝桥杯2017年第八届真题-发现环（C++代码）并查集

1273 阅读 3 评论 5 点赞

原题链接：蓝桥杯2017年第八届真题-发现环

#include "stdio.h"
    #include "stdlib.h"
    #include "iostream"
    #include "string.h"
    #include "math.h"
    #include "algorithm"
    #include "queue"
    #include "vector"
    #include "map"
    using namespace std;
    const int maxn = 100005;
    vector<int>G[maxn];    //关系图，这里使用动态数组，为了节省不必要的空间
    int fa[maxn];        //并查集数组
    int n;
    int sx, fy;        //起点和终点
    bool vis[maxn];    //用于做标记，判断当前结点是否已经访问过
    int res[maxn];    //结果数组，用于保存所有在环上的点
    //并查集核心代码（带路径压缩）
    int find(int x){
       return x == fa[x] ? x : fa[x] = find(fa[x]);
    }
    //x：当前结点 ----- len：结果数组长度
    void dfs(int x, int len){
       res[len] = x;    //把当前在环上的结点存到结果数组中
       if(x == fy){    //如果当前结点已经访问到fy，则此环已经访问完毕，直接输出结果即可
           sort(res, res + len + 1);    //应题目要求，输出前先进行排序
           for (int i = 0; i <= len; ++i) {
               printf("%d ", res[i]);
           }
           cout << endl;
           return ;
       }
       vis[x] = 1;    //标记此结点已被访问过
       for (int i = 0; i < G[x].size(); ++i) {    //枚举x的关系表中所有连通的结点
           if(!vis[G[x][i]]){        //如果G[x][i]这个结点没有被访问过，则递归进行访问
               dfs(G[x][i], len + 1);    //结果数组长度要+1，否则会造成覆盖
           }
       }
       vis[x] = 0;    //回溯
    }
    int main(){
       scanf("%d", &n);
       for (int i = 1; i <= n; ++i) {
           fa[i] = i;
       }
       for (int i = 1; i <= n; ++i) {
           int x, y;
           scanf("%d%d", &x, &y);
           int p1 = find(x);
           int p2 = find(y);
           if(p1 != p2) {    //如果当前两点没有连通，则把两点进行连通，并建立关系表
               fa[p2] = p1;
               G[x].push_back(y);    //当前x结点连通y结点
               G[y].push_back(x);    //当前y结点连通x结点
           }else {    //如果当前两点已经连通则表明这两点必然在环上，记录两点，用于搜索
               sx = x;
               fy = y;
           }
       }
        //从sx为起点搜索到fy结束
       dfs(sx, 0);
       return 0;
    }

0.0分

7 人评分

本文分类：题解列表
浏览次数：1273 次浏览
发布日期：2019-05-19 14:37:49
本文链接：https://blog.dotcpp.com/a/60008

上一篇 > 字符串中间和后边*号删除（C语言代码）
下一篇 > 回文判断（C/C++语言代码）

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

蓝桥杯2017年第八届真题-发现环（C++代码）并查集

评论列表共有 3 条评论

发表评论取消回复

蓝桥杯2017年第八届真题-发现环 （C++代码）并查集

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 3 条评论

发表评论 取消回复

蓝桥杯2017年第八届真题-发现环（C++代码）并查集

评论列表共有 3 条评论

发表评论取消回复