代码随想录算法训练营Day48 | 108.冗余连接、109.冗余连接II
KamaCoder108.冗余连接
108. 多余的边
1.思路
对于边(s, t)，使用find(s)和find(t)分别查找s和t所在集合的根节点。
如果根节点相同：说明s和t本来就在同一个集合中，即它们已经连通。此时，边(s, t)的加入必定会形成环。这就是我们要找的第一条成环边，直接输出(s, t)并结束程序。
如果根节点不同：说明s和t尚未连通。此时，使用join(s, t)将它们所在的两个集合合并，表示它们现在连通了。然后继续处理下一条边。
#include <iostream> #include <vector> using namespace std; int n; vector<int>father(1005,1); void init(){ for(int i=1;i<=n;i++){ father[i]=i; } } int find(int u){ if(u==father[u]){ return u; } return father[u]=find(father[u]); } // 将v->u 这条边加入并查集 int join(int u,int v){ u=find(u); v=find(v); if(u==v) return 0; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回 father[u]=v; return 1; } int main(){ cin>>n; init(); for(int i=0;i<n;i++){ int s,t;cin>>s>>t; if(!join(s,t)){ cout<<s<<" "<<t<<endl; break; } } return 0; }2.思考
这道题只需要在合并的时候判断两个节点的父节点是否相同即可，相同则说明两节点已经在同一集合了，直接输出当前两节点。
3.Reference：108. 多余的边
KamaCoder109.多余的边II
109. 多余的边II
1.思路
这个图最初是一棵有n个节点的树（有n-1条边），然后被额外添加了一条有向边。由于添加了这条边，图可能不再是一棵树。这会导致两种可能的问题：
存在环：新添加的边连接了已经连通的两个节点；存在入度为2的节点：新添加的边指向了一个已经有入边的节点。
目标：找出这条被添加的“冗余”边，移除它后，图能重新变为一棵树。
情况一：存在入度为 2 的节点 (vec.size() > 0)
冗余边必定是edge1或edge2中的一条，我们需要判断到底是哪一条。
首先尝试删除vec[1]对应的边，如果isdelete返回true，说明删除edge2后图是合法的， 那么edge2就是答案。如果isdelete返回false，说明删除edge2后图仍然有环。这意味 着edge1才是构成环的边，因此edge1是答案。
情况二：不存在入度为 2 的节点 (vec.size() == 0)
既然没有入度为 2 的节点，那么问题必定是存在一个环。而且，这个环就是由那条多 余的边造成的。
直接使用并查集遍历所有n条边，找到第一个构成环的边即可。
如果issame(u, v)为true，说明u和v已经连通，当前边(u, v)就是导致环的冗余边。直 接输出并结束程序。
如果issame(u, v)为false，则执行join(u, v)，继续检查下一条边。
#include <iostream> #include <vector> using namespace std; int n; vector<int>father(1005,1); void init(){ for(int i=1;i<=n;i++){ father[i]=i; } } int find(int u){ if(u==father[u]){ return u; } return father[u]=find(father[u]); } bool issame(int u,int v){ u=find(u); v=find(v); return u==v; } void join(int u,int v){ u=find(u); v=find(v); if(u==v) return; father[u]=v; } // 删一条边之后判断是不是树 bool isdelete(vector<pair<int,int>>&edges,int u){ init(); for(int i=1;i<=n;i++){ if(i==u) continue; if(issame(edges[i].first,edges[i].second)){ // 构成有向环了，一定不是树 return false; } else join(edges[i].first,edges[i].second); } return true; } int main(){ cin>>n; vector<pair<int,int>>edges(n+1); // 存边 vector<int>indegree(n+1,0); // 记录节点入度 for(int i=1;i<=n;i++){ int s,t;cin>>s>>t; edges[i]={s,t}; indegree[t]++; } vector<int>vec; // 找入度为2的节点所对应的边 for(int i=1;i<=n;i++){ if(indegree[edges[i].second]==2){ vec.push_back(i); } } if(vec.size()>0){ // 优先删vec[1] 对应这条边 if(isdelete(edges,vec[1])){ cout<<edges[vec[1]].first<<" "<<edges[vec[1]].second<<endl; } else cout<<edges[vec[0]].first<<" "<<edges[vec[0]].second<<endl; return 0; } // 明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了 // 在有向图里找到删除的那条边，使其变成树 init(); for(int i=1;i<=n;i++){ if(issame(edges[i].first,edges[i].second)){ cout<<edges[i].first<<" "<<edges[i].second<<endl; return 0; } else join(edges[i].first,edges[i].second); } return 0; }2.思考
这道题较上道题难度天差地别。有多余的边，我们就要讨论几种情况，第一种就是有入度为 2 的节点，那么显而易见，该节点相关的两条边中的一条就是冗余的边，那么此时我们就假设删除第二条边，然后看剩余边能否构成有向树，如果能，那么该条边就是冗余的，否则，第一条边就是冗余的；还有一种情况就不存在入度为 2 的节点，但此时还是存在冗余边，所以就是形成了环，此时也就来到了 多余的边 那道题的情况，只需要依次连接节点，遇到在同一集合的两节点，立即输出返回，此时两节点构成的边即为多余的边。