列公子

用户名：lielielie

访问量：10578

签　名：

等　　级
排　　名	1695
经　　验	2703
参赛次数	0
文章发表	20
年　　龄	0
在职情况	学生
学　　校	哈尔滨工程大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯路径之谜 DFS
浏览：132

1924题 - 01背包 - 动态规划 + 一维数组空间优化
浏览：535

你可能喜欢

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

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

C语言程序设计教程（第三版）课后习题8.6 （C++代码）不是所有的时候都要按照题目要求才能AC

蓝桥杯发现环 DFS+并查集

　　作者: 列公子　　　　发表时间：2020-03-12 13:36:15 浏览：483　|　评论：0　

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

# 蓝桥杯2017年第八届真题  发现环  DFS+并查集

## 1. 思路

1. 并查集 代表**连通分支**, 当然, 属于同一个连通分支的节点一定彼此连通

2. 在输入边时, 合并连通分支, 如果两个节点**已经连通**(即已经属于相同连通分支), 新加入的边与之前的若干条边**构成环路**, 分别以这两个节点作为搜索的 起点 和 终点

3. 一边搜索一边保存搜索到的节点, 搜索到终点时, 按序输出

## 2. 完整代码 (AC)
```cpp
//
// 蓝桥杯真题 发现环
// DFS + 并查集
//
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 100005;

vector<int> path;            // 当前路径
bool vis[maxn];

vector<int> G[maxn];        // 临接表

int father[maxn];       // 并查集

int getFather(int x){   // 找并查集 根节点, 同时路径压缩
    int t = x;
    while (father[x] != x)
        x = father[x];
    // x 已为根, 开始压缩路径
    while (t != x){
        int curF = father[t];
        father[t] = x;
        t = curF;
    }
    return x;
}

// 起点, 终点
int s, d;

void dfs(int node){
    vis[node] = true;
    path.push_back(node);

if (node == d){
        if (path.size() == 2)
            return;
        // 题目要求排序输出
        sort(path.begin(), path.end());
        for (int i = 0; i < path.size(); i++)
            printf("%d ", path[i]);

return;
    }

for (int i = 0; i < G[node].size(); i++){
        int cur = G[node][i];
        if (!vis[cur])
            dfs(cur);
    }
    path.pop_back();
    vis[node] = false;
}

int main(){
    int N;
    scanf("%d", &N);
    // 初始化并查集
    for (int i = 1; i <= N; i++)
        father[i] = i;

for (int i = 0; i < N; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        if (a > b)
            swap(a, b);

int ra = getFather(a);
        int rb = getFather(b);

// ra 和 rb 已经连通, 新加入的边 (a, b) 构成环
        if (ra == rb){
            s = a;  // 起点
            d = b;  // 终点
        } else     // 否则合并连通分支
            father[b] = a;

G[a].push_back(b);
        G[b].push_back(a);
    }

dfs(s);
    return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

列公子

TA的其他文章

你可能喜欢

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

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

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

C语言程序设计教程（第三版）课后习题8.6 （C++代码）不是所有的时候都要按照题目要求才能AC

整除问题（C语言代码）

蓝桥杯发现环 DFS+并查集

评论区

精彩推荐

点我有惊喜！你懂得！

小九九（C语言代码）

矩阵转置（C语言代码）

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

A+B for Input-Output Practice (III) （C语言代码）

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

模拟计算器（C++代码）

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

局部变量作函数返回值的问题

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

列公子

TA的其他文章

你可能喜欢

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

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

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

C语言程序设计教程（第三版）课后习题8.6 （C++代码）不是所有的时候都要按照题目要求才能AC

整除问题 （C语言代码）

蓝桥杯 发现环 DFS+并查集

评论区

精彩推荐

点我有惊喜！你懂得！

小九九 （C语言代码）

矩阵转置 （C语言代码）

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

A+B for Input-Output Practice (III) （C语言代码）

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

模拟计算器 （C++代码）

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

局部变量作函数返回值的问题

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

整除问题（C语言代码）

蓝桥杯发现环 DFS+并查集

　　评论区

小九九（C语言代码）

矩阵转置（C语言代码）

模拟计算器（C++代码）