zjh

用户名：speaksoftly

访问量：24718

签　名：

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

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

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-统计单词数-题解(C++代码) map计数
浏览：690

逆序数（C++代码）正解：线段树(nlogn)单点查询区间更新
浏览：363

信息学奥赛一本通T1242-网线主管（C++代码）二分
浏览：1468

你可能喜欢

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

　　作者: zjh　　　　发表时间：2019-05-19 14:37:49 浏览：1057　|　评论：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语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

【数组的距离】（C语言代码）

拆分位数（C++代码）用char简单粗暴，嗯

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

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

评论区

精彩推荐

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

C二级辅导-等差数列（C语言代码）

【回文数(二)】（C语言代码）

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

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

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

简单的a+b （C语言代码）

printf基础练习2 （有点不明白）

IP判断（C语言代码）

zjh

TA的其他文章

你可能喜欢

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

C二级辅导-阶乘数列 （C语言代码）

【数组的距离】 （C语言代码）

拆分位数 （C++代码）用char简单粗暴，嗯

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

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

评论区

精彩推荐

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

C二级辅导-等差数列 （C语言代码）

【回文数(二)】 （C语言代码）

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

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

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

简单的a+b （C语言代码）

printf基础练习2 （有点不明白）

IP判断 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

【数组的距离】（C语言代码）

拆分位数（C++代码）用char简单粗暴，嗯

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

　　评论区

C二级辅导-等差数列（C语言代码）

【回文数(二)】（C语言代码）

IP判断（C语言代码）