zjh

用户名：speaksoftly

访问量：22703

签　名：

搞spring去了...不能愉快的刷题了...

等　　级
排　　名	174
经　　验	6732
参赛次数	10
文章发表	37
年　　龄	0
在职情况	学生
学　　校	海南
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-数的划分-题解(C++代码)蒟蒻的me也来写一写题解
浏览：884

蓝桥杯历届试题-国王的烦恼（C++代码）并查集&生成树
浏览：812

蓝桥杯历届试题-城市建设（C++代码）并查集&最小生成树kruskal
浏览：1160

你可能喜欢

C语言程序设计教程（第三版）课后习题3.7 （Java代码）

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

　　作者: zjh　　　　发表时间：2019-05-19 14:37:49 浏览：999　|　评论：2　

原题链接：蓝桥杯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 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

一个人的巴黎

for (int i = 0; i < G[x].size(); i++)//枚举x的关系表中所有连通的结点
	{
		int f = G[x][i];
		if (vis[G[x][i]] == 0)
		{
			vis[f] = 1;
			dfs(f, step + 1);
			vis[f] = 0;
		}
	}
为什么我不能在for循环里面判断是否访问过该节点呢？这样只会对30%

2022-01-25 22:29:17

沐白

赞，思路清晰

2020-03-15 09:12:17

zjh

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题3.7 （Java代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-温度转换（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

点我有惊喜！你懂得！

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

评论区

精彩推荐

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）如果a<0，那就不是这个代码了，哈哈哈哈

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

【矩阵】（C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

大家好，我是验题君

【偶数求和】（C语言代码）

数列问题（C语言代码）

zjh

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题3.7 （Java代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-温度转换 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

点我有惊喜！你懂得！

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

评论区

精彩推荐

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码） 如果a<0，那就不是这个代码了，哈哈哈哈

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

【矩阵】 （C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

大家好，我是验题君

【偶数求和】 （C语言代码）

数列问题 （C语言代码）

C二级辅导-温度转换（C语言代码）

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

　　评论区

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）如果a<0，那就不是这个代码了，哈哈哈哈

【矩阵】（C++代码）

【偶数求和】（C语言代码）

数列问题（C语言代码）