首页 > 其他分享 >第五十六天 第十一章:图论part06 108.冗余连接 109. 冗余连接II

第五十六天 第十一章:图论part06 108.冗余连接 109. 冗余连接II

时间:2024-07-31 14:52:56浏览次数:14  
标签:vector int 查集 节点 init edges 第五十六 连接 冗余

108. 冗余连接

继续使用查并集的方法,如果两个元素是在一个集合,那么我们就输出,反之加入集合。

#include<iostream>
#include<vector>
using namespace std;

int N;
vector<int> father=vector<int>(1001,0);

void init(){
    for(int i=0;i<=N;i++){
    father[i]=i;
    }
}

int find(int u){
    if(father[u]==u) return u;
    else return father[u]= find(father[u]);
}

bool compare(int s,int t){
    s=find(s);
    t=find(t);
    return s==t;
}

void join(int s,int t){
    s=find(s);
    t=find(t);
    if(s==t) return;
    else father[s]=t;
}

int main(){
    cin>>N;
    int i,j;
    init();
    while(N--){
        cin>>i>>j;
        if(compare(i,j)) 
        {
         cout<<i<<" "<<j<<endl;
         return 0;
        }
        else  join(i,j);
    }
}

109. 冗余连接II

我们要解决本题要实现两个最为关键的函数:

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

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

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

#include<iostream>
#include<vector>

using namespace std;

int N;
vector<int> father=vector<int>(1001,0);

void init(){
    for(int i=0;i<=N;i++){
        father[i]=i;
    }
}

int find(int u){
    if(u==father[u]) return u;
    else return father[u]=find(father[u]);
}

bool compare(int s,int t){
    s=find(s);
    t=find(t);
    return s==t;
}

void join(int s,int t){
    s=find(s);
    t=find(t);
    if(s==t) return;
    father[s]=t;
}

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

void getRemoveEdge(const vector<vector<int>>& edges) {
    init(); // 初始化并查集
    for (int i = 0; i < N; i++) { // 遍历所有的边
        if (compare(edges[i][0], edges[i][1])) { // 构成有向环了,就是要删除的边
            cout << edges[i][0] << " " << edges[i][1];
            return;
        } else {
            join(edges[i][0], edges[i][1]);
        }
    }
}


int main(){
    int s,t;
    vector<vector<int>> edges;
    cin>>N;
    vector<int> isDegree(N+1);//记录节点入度数
    for(int i=0;i<N;i++){
        cin>>s>>t;
        isDegree[t]++;
        edges.push_back({s,t});
    }
     //记录度为二的边
     //找入度为2的节点所对应的边,注意要倒序,因为优先删除最后出现的一条边
     vector<int> vec;
     for(int i=N-1;i>=0;i--){
         if(isDegree[edges[i][1]]==2)  vec.push_back(i);
     }
    if(vec.size()>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;
    }
    getRemoveEdge(edges);
}

标签:vector,int,查集,节点,init,edges,第五十六,连接,冗余
From: https://blog.csdn.net/m0_69189584/article/details/140821781

相关文章

  • 尝试使用 pyodbc 连接到 SQL Server 数据库时出现操作错误
    我正在尝试使用Python3中的pyodbc连接到SQLServer数据库。但是当我尝试建立连接时出现错误。我做了这样的事情:importpyodbcconn=pyodbc.connect('Driver={ODBCDriver18forSQLServer};Server=192.168.2.250;Database=DB;UID=username;PWD=password;')......
  • 浏览器弹出“您与此网站的建立的连接不安全”怎么办——三步消除此提示
     上网看剧、购物等等已经成为我们生活中不可缺少的一部分,但有时我们打开浏览器浏览一些网站时,会弹出“网站连接不安全”的显示。这是为什么?该怎么办?其实,这是由于该网站使用了HTTP协议传输数据,浏览器警告用户谨慎访问此网站。之所以会有此“不安全”警告,是因为使用HT......
  • STM32F103+FreeRTOS的使用ESP8266与手机APP实现TCP连接通信控制
    前言本人初学FreeRTOS,来自不知名普通院校,大二物联网专业,简单看完百问网韦东山老师FreeRTOS就想随便找个小项目试试看,手头里没什么元器件,只有一块ESP8266wifi模块以及温湿度模块显示屏模块,所以用到的模块不多,这俩个模块可能不太适用于FreeRTOS,但主要目的想着以最少的资源练练......
  • 【YashanDB知识库】ycm纳管主机安装YCM-AGENT时报错“任务提交失败,无法连接主机”
    问题现象执行安装ycm-agent命令纳管主机时报错问题的风险及影响会导致ycm-agent纳管不成功,YCM无法监控主机和数据库问题影响的版本yashandb-cloud-manager-23.2.1.100-linux-aarch64.tar问题发生原因因为10.149.223.121对ycm的主机没有开放端口9070或9071解决方法及规避......
  • 使用finallshell连接linux
    用户可以去FinalShell的官网上下载,只需点击下载地址,即可轻松下载安装包。傻瓜式安装点击到底。使用双击打开页面,新建连接右击连接,新建》ssh 连接,双击新建的连接,如下界面即连接成功。新建文件夹,右键新建文件夹。新建文件,在文件夹右键新建文件。命令在命令区域正......
  • netty核心流程(一):服务端如何建立连接
    为了接收连接请求,Netty服务端应该做些什么事情?根据JavaNIO的知识,服务端在准备接收客户端连接之前做了下面几个工作,我们可以带着问题往下看。服务端对连接请求是如何初始化的?如何把用户定义的处理逻辑childHandler加入到Netty的处理流程里?如何在Socket上绑定一个端......
  • 避免字符串连接的嵌套循环的 Pythonic 方法
    我想找到所有5位数字的字符串,其中前三位数字在我的第一个列表中,第二个槽第四个数字在我的第二个列表中,第三到第五个数字在我的最后一个列表中:l0=["123","567","451"]l1=["234","239","881"]l2=["348","551","399"......
  • todesk远程连接软件安装linux版本
    统信UOS、麒麟OS、方德debpackage:https://dl.todesk.com/linux/todesk-v4.7.2.0-amd64.deb立即下载(使用4.7.2.0覆盖安装后,临时密码将会变更)安装命令:01.sudoapt-getinstalllibappindicator3-dev02.sudoapt-getinstall./todesk-v4.7.2.0-amd64.deb 复制代码启......
  • Python MySQL 无法连接,原因不明
    当我尝试使用python连接到我的MySQL数据库时,由于未知原因显示错误:dTraceback(mostrecentcalllast):File"/usr/local/bin/flask",line8,in<module>sys.exit(main())^^^^^^File"/usr/local/lib/python3.12/site-packages/flask/cli.py&......
  • 虚拟机:GCC共享库在连接时的搜索位置和优选次序
    假设有两个相同的共享库,一个在标准的共享库搜索目录(/lib/i386-linux-gnu),一个在非标准目录(/home/charles/tmp):在/home/charles/tmp下有个测试程序main.c,调用共享库里的函数。用如下的命令编译:用ldd看一下link的共享库:可以看出,虽然我们指定了要使用/home/charles/tmp下的......