代码随想录算法训练营第四十八天 | 卡码网108. 多余的边、卡码网109. 多余的边II

卡码网108. 多余的边

题目链接：卡码网108. 多余的边
思路：并查集的join()函数是将边加入并查集中，从这个入手，u 和 v 寻根之后如果相等，说明是多余的边。

#include<iostream>#include<vector>usingnamespacestd;intn;vector<int>father(1001,0);voidinit(){for(inti=0;i<n;++i){father[i]=i;}}intfind(intx){if(x==father[x])returnx;elsereturnfather[x]=find(father[x]);}voidjoin(intu,intv){introotU=find(u);introotV=find(v);if(rootU==rootV){cout<<u<<" "<<v<<endl;return;}father[rootV]=rootU;}intmain(){cin>>n;init();for(inti=0;i<n;++i){ints,t;cin>>s>>t;join(s,t);}return0;}

也可以写出完整的join()函数和isSame()函数，在主函数中判断，如果isSame()返回true，打印输出并返回，否则就用join()函数加边。

卡码网109. 多余的边II

题目链接：卡码网109. 多余的边II
看题解了！
分析：

#include<iostream>#include<vector>usingnamespacestd;intn;vector<int>father(1001,0);voidinit(){for(inti=0;i<n;++i){father[i]=i;}}intfind(intx){if(x==father[x])returnx;elsereturnfather[x]=find(father[x]);}voidjoin(intu,intv){u=find(u);v=find(v);if(u==v)return;father[v]=u;}boolisSame(intu,intv){u=find(u);v=find(v);returnu==v;}boolisTreeDeleteEdge(constvector<vector<int>>&edges,intdeleteEdge){init();for(inti=0;i<edges.size();++i){if(i==deleteEdge)continue;// 不加入并查集intu=find(edges[i][0]);intv=find(edges[i][1]);if(u==v)returnfalse;elsejoin(edges[i][0],edges[i][1]);}returntrue;}intmain(){cin>>n;init();vector<vector<int>>edges(n,vector<int>(2,0));// 存储边的信息vector<int>indeg(n+1,0);// 存储入度个数for(inti=0;i<n;++i){cin>>edges[i][0]>>edges[i][1];indeg[edges[i][1]]++;// 统计入度个数}// 找出入度为2的边，倒叙存储， 方便找出最后出现的边vector<int>vec;for(inti=n-1;i>=0;--i){if(indeg[edges[i][1]]==2){vec.push_back(i);// 第 i 条边}}// 情况1：有入度为2的边if(vec.size()>0){if(isTreeDeleteEdge(edges,vec[0])){cout<<edges[vec[0]][0]<<" "<<edges[vec[0]][1]<<endl;return0;}else{cout<<edges[vec[1]][0]<<" "<<edges[vec[1]][1]<<endl;return0;}}// 情况2：没有入度为2的边 , 检查是否成环for(inti=0;i<edges.size();++i){intu=find(edges[i][0]);intv=find(edges[i][1]);if(u==v){cout<<edges[i][0]<<" "<<edges[i][1]<<endl;return0;}elsejoin(edges[i][0],edges[i][1]);}return0;}

分析、拆解，分情况讨论！！！