博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
leetcode_684. Redundant Connection
阅读量:6466 次
发布时间:2019-06-23

本文共 1026 字,大约阅读时间需要 3 分钟。

一个无向图,n个顶点有n条边,输出一条可以删除的边,删除后使得图成为一棵树。可以使用并查集解决。

class Solution{public:    int father[1001];    void initfather()    {        for(int i=1; i<=1000; i++)            father[i]=i;    }    int findFather(int x)    {        if(father[x]!=x)            father[x] = findFather(father[x]);        return father[x];    }    void Merge(int x1, int x2)    {        int father_x1 = findFather(x1);        int father_x2 = findFather(x2);        if(father_x1 != father_x2)            father[father_x2] = father_x1;    }    vector
findRedundantConnection(vector
>& edges) { initfather(); vector
res; for(auto edge:edges) { int u = edge[0]; int v = edge[1]; if(findFather(u) == findFather(v)) { res=edge; break; } else Merge(u,v); } return res; }};

 

转载于:https://www.cnblogs.com/jasonlixuetao/p/10695777.html

你可能感兴趣的文章
向Docx4j生成的word文档中添加布局--第二部分
查看>>
股市和战争
查看>>
PHP时间戳和日期相互转换(文字有问题)
查看>>
WPF水珠效果按钮组
查看>>
算法逆向6——RSA识别
查看>>
【TensorFlow】学习笔记
查看>>
互联网黑产剖析——虚假号码
查看>>
node.js和前端js有什么区别
查看>>
CDN介绍
查看>>
极大似然估计的理解与应用
查看>>
读MBA经历回想(下)做法决定结果——北漂18年(49)
查看>>
Win7如何显示文件后缀
查看>>
Android远程桌面助手(B1185)for Android P开发者预览版
查看>>
【Excle】二维表转化为一维表
查看>>
我的Quartz笔记
查看>>
Hadoop学习之路(十九)MapReduce框架排序
查看>>
转头条:阿里p7架构师:三年经验应该具备什么样的技能?
查看>>
VS2008中MFC对话框界面编程Caption中文乱码的解决办法
查看>>
mysql优化——慢日志、Percona Toolkit、SHOW PROFILE、performance_schema【转】
查看>>
SpringMVC method属性与http请求方法一致
查看>>