算法日记 46 day 图论（并查集）

🕗 发布于 2024-12-11 05:33 算法图论

题目：冗余连接

108. 冗余连接 (kamacoder.com)

题目描述

有一个图，它是一棵树，他是拥有 n 个节点（节点编号1到n）和 n - 1 条边的连通无环无向图（其实就是一个线形图），如图：

现在在这棵树上的基础上，添加一条边（依然是n个节点，但有n条边），使这个图变成了有环图，如图：

先请你找出冗余边，删除后，使该图可以重新变成一棵树。

输入描述

第一行包含一个整数 N，表示图的节点个数和边的个数。

后续 N 行，每行包含两个整数 s 和 t，表示图中 s 和 t 之间有一条边。

输出描述

输出一条可以删除的边。如果有多个答案，请删除标准输入中最后出现的那条边。

题目分析：

首先明确并查集解决的问题是两个数是否在同一个集合中，也可以让两个数加入一个集合。

题目要求删除冗余边，冗余边是怎么产生的呢？是两个结点都连着一个结点之后，这两个结点也相连了，这么一看，我们只需要判断，两个结点在不在同一个集合中，如果在的话，新加入的边是不是就是冗余边了呢。

所以，这一题也是并查集的问题，看看代码

#include<iostream>
#include<vector>
 
using namespace std;
 
int n;
vector<int> father(1001,0);
 
void init(){
    for(int i=0;i<=n;i++){
        father[i]=i;
    }
}
 
int find(int u){
    return u==father[u]?u:father[u]=find(father[u]);
}
 
void join(int u,int v){
    u=find(u);
    v=find(v);
    if(u==v) return;
    father[v]=u;
}
 
bool isSame(int u,int v){
    u=find(u);
    v=find(v);
    if(u==v) return true;
    return false;
}
 
 
int main(){
    int s,t;
    cin>>n;
    init();//初始化
    for(int i=0;i<n;i++){
        cin>>s>>t;
        if(isSame(s,t)){
            cout << s << " " << t << endl;
            return 0;
        }
        else{
            join(s,t);
        }
    }
     
     
}

题目：冗余连接 2

109. 冗余连接II (kamacoder.com)

题目描述

有一种有向树,该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。有向树拥有 n 个节点和 n - 1 条边。如图：

现在有一个有向图，有向图是在有向树中的两个没有直接链接的节点中间添加一条有向边。如图：

输入一个有向图，该图由一个有着 n 个节点(节点编号从 1 到 n)，n 条边，请返回一条可以删除的边，使得删除该条边之后该有向图可以被当作一颗有向树。

输入描述

第一行输入一个整数 N，表示有向图中节点和边的个数。

后续 N 行，每行输入两个整数 s 和 t，代表这是 s 节点连接并指向 t 节点的单向边

输出描述

输出一条可以删除的边，若有多条边可以删除，请输出标准输入中最后出现的一条边。

题目分析：

不同于之前的无向图连接，这次换成了有向图，相比于无向图来说，有向图冗余边的判断就较为复杂。

情况一：

如果我们找到入度为2的点，那么删一条指向该节点的边就行了。

如图：

找到了节点3 的入度为2，删 1 -> 3 或者 2 -> 3 。选择删顺序靠后便可。

但入度为2 还有一种情况，情况二，只能删特定的一条边，如图：

节点3 的入度为 2，但在删除边的时候，只能删这条边（节点1 -> 节点3），如果删这条边（节点4 -> 节点3），那么删后本图也不是有向树了（因为找不到根节点）。

综上，如果发现入度为2的节点，我们需要判断删除哪一条边，删除后本图能成为有向树。如果是删哪个都可以，优先删顺序靠后的边。

情况三：如果没有入度为2的点，说明图中有环了（注意是有向环）。

如图：

对于情况三，删掉构成环的边就可以了。

既然要对入度进行分析，那么我们就需要对每一边的入度进行统计了

    int s, t;
    vector<vector<int>> edges;
    cin >> n;
    vector<int> inDegree(n + 1, 0); // 记录节点入度
    for (int i = 0; i < n; i++) {
        cin >> s >> t;
        inDegree[t]++;
        edges.push_back({s, t});
    }

那么在统计完成之后，就需要找到入度为2的结点，题目要求删除最后一条边，所以我们倒序遍历即可。

vector<int> vec; // 记录入度为2的边（如果有的话就两条边）
// 找入度为2的节点所对应的边，注意要倒序，因为优先删除最后出现的一条边
for (int i = n - 1; i >= 0; i--) {
    if (inDegree[edges[i][1]] == 2) {
        vec.push_back(i);
    }
}
if (vec.size() > 0) {
    // 放在vec里的边已经按照倒叙放的，所以这里就优先删vec[0]这条边
    if (isTreeAfterRemoveEdge(edges, vec[0])) {
        cout << edges[vec[0]][0] << " " << edges[vec[0]][1];
    } else {
        cout << edges[vec[1]][0] << " " << edges[vec[1]][1];
    }
    return 0;
}

再来看情况3，没有入度为2 的结点，但是也构成了环，那么删除掉构成环的边，我们单独写一个函数来移除这一条边。

所以总的来说就是两个主要的函数，

isTreeAfterRemoveEdge() 判断删一个边之后是不是有向树
getRemoveEdge() 确定图中一定有了有向环，那么要找到需要删除的那条边

isTreeAfterRemoveEdge() 判断删一个边之后是不是有向树：将所有边的两端节点分别加入并查集，遇到要要删除的边则跳过，如果遇到即将加入并查集的边的两端节点本来就在并查集了，说明构成了环。

如果顺利将所有边的两端节点（除了要删除的边）加入了并查集，则说明删除该条边还是一个有向树

getRemoveEdge()确定图中一定有了有向环，那么要找到需要删除的那条边：将所有边的两端节点分别加入并查集，如果遇到即将加入并查集的边的两端节点本来就在并查集了，说明构成了环。

来看看代码

#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> father (1001, 0);
// 并查集初始化
void init() {
    for (int i = 1; i <= n; ++i) {
        father[i] = i;
    }
}
// 并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]);
}
// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return ;
    father[v] = u;
}
// 判断 u 和 v是否找到同一个根
bool same(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 在有向图里找到删除的那条边，使其变成树
void getRemoveEdge(const vector<vector<int>>& edges) {
    init(); // 初始化并查集
    for (int i = 0; i < n; i++) { // 遍历所有的边
        if (same(edges[i][0], edges[i][1])) { // 构成有向环了，就是要删除的边
            cout << edges[i][0] << " " << edges[i][1];
            return;
        } else {
            join(edges[i][0], edges[i][1]);
        }
    }
}

// 删一条边之后判断是不是树
bool isTreeAfterRemoveEdge(const vector<vector<int>>& edges, int deleteEdge) {
    init(); // 初始化并查集
    for (int i = 0; i < n; i++) {
        if (i == deleteEdge) continue;
        if (same(edges[i][0], edges[i][1])) { // 构成有向环了，一定不是树
            return false;
        }
        join(edges[i][0], edges[i][1]);
    }
    return true;
}

int main() {
    int s, t;
    vector<vector<int>> edges;//存储所有边的信息
    cin >> n;
    vector<int> inDegree(n + 1, 0); // 记录节点入度
    for (int i = 0; i < n; i++) {
        cin >> s >> t;
        inDegree[t]++;
        edges.push_back({s, t});
    }

    vector<int> vec; // 记录入度为2的边（如果有的话就两条边）
    // 找入度为2的节点所对应的边，注意要倒序，因为优先删除最后出现的一条边
    for (int i = n - 1; i >= 0; i--) {
        if (inDegree[edges[i][1]] == 2) {
            vec.push_back(i);
        }
    }
    // 情况一、情况二
    if (vec.size() > 0) {
        // 放在vec里的边已经按照倒叙放的，所以这里就优先删vec[0]这条边
        if (isTreeAfterRemoveEdge(edges, vec[0])) {
            cout << edges[vec[0]][0] << " " << edges[vec[0]][1];
        } else {
            cout << edges[vec[1]][0] << " " << edges[vec[1]][1];
        }
        return 0;
    }

    // 处理情况三
    // 明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了
    getRemoveEdge(edges);
}

对于更详细的解析与其他语言的代码块，可以去代码随想录上查看。

代码随想录 (programmercarl.com)

已刷题目：141

原文地址：https://blog.csdn.net/weixin_70808146/article/details/144382331

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：ThinkPHP开发的原生微信小程序二手物品回收小程序管理系统源码
下一篇：开源模型应用落地-知识巩固-生产级AI服务优化（二）

.NET(C#) 如何配置用户首选项及保存用户设置
.NET(C#) 如何配置用户首选项及保存用户设置
阅读更多2024-12-14
【最新】北大数字普惠金融指数数据集-省市县（2011-2023年）
郭峰,王靖一,王芳,孔涛,张勋,程志云.测度中国数字普惠金融发展:指数编制与空间特征[J].经济学(季刊),2020,19(04):1401-1418.时间跨度：省级和城市级指数时间跨度为2011-2
阅读更多2024-12-14
GESP202412 四级【Recamán】题解（AC）
a11ak−1−kkakak−1−kak−1k小杨想知道 Recamán 数列的前n项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
阅读更多2024-12-14
IDEA遇到EasyConnect中的网络资源无法访问的问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/wanshanyu_/article/de
阅读更多2024-12-14
双目摄像头标定方法
此时已经完成标定，左下角为反投影误差，右边为外参可视化。将双目左右目拍的图像上传（左右目最好不少于20张）此时回到主页面，即可看到成功导出。把这些误差大的删除即可。
阅读更多2024-12-14
Servlet、omcat服务器架构与工作原理
Servlet是运行在服务器端的Java程序，它的主要职责之一是接收并处理来自客户端（如浏览器）的HTTP请求。当客户端发送一个请求到服务器时，Servlet可以解析请求中的信息，例如请求的URL路径
阅读更多2024-12-14
Vue生命周期钩子函数：深入解析与实践
作为高级Vue前端开发人员，对Vue组件的生命周期钩子函数有着深刻的理解是至关重要的。生命周期钩子函数是指在Vue组件的创建、更新、销毁等过程中，Vue自动调用的一系列方法。通过这些钩子函数，我们可以
阅读更多2024-12-14
安卓开发--使用android studio发布APP
app发布
阅读更多2024-12-14
数据结构与算法学习笔记----拓扑排序
@ author: 明月清了个风。
阅读更多2024-12-14
python 将数据保存到现有的Excel文件的新工作表
out_file = ‘query.xlsx’df1 = pd.DataFrame(out_data)若直接写入：df1.to_excel(out_file, index=False, sheet_n
阅读更多2024-12-14

算法日记 46 day 图论（并查集）

题目：冗余连接

题目分析：

题目：冗余连接 2

题目分析：

已刷题目：141

相关文章