哈尔滨网站建设王道下拉強个人简历网官网

哈尔滨网站建设王道下拉強,个人简历网官网,汕尾海丰建设规划局网站,长沙网站建设规划KamaCoder108.冗余连接 108. 多余的边 1.思路 对于边 (s, t)#xff0c;使用 find(s) 和 find(t) 分别查找 s 和 t 所在集合的根节点。 如果根节点相同#xff1a;说明 s 和 t 本来就在同一个集合中#xff0c;即它们已经连通。此时#xff0c;边 (s, t) 的加入必定会形成…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; vectorintfather(1005,1); void init(){ for(int i1;in;i){ father[i]i; } } int find(int u){ if(ufather[u]){ return u; } return father[u]find(father[u]); } // 将v-u 这条边加入并查集 int join(int u,int v){ ufind(u); vfind(v); if(uv) return 0; // 如果发现根相同则说明在一个集合不用两个节点相连直接返回 father[u]v; return 1; } int main(){ cinn; init(); for(int i0;in;i){ int s,t;cinst; if(!join(s,t)){ couts tendl; break; } } return 0; }2.思考这道题只需要在合并的时候判断两个节点的父节点是否相同即可相同则说明两节点已经在同一集合了直接输出当前两节点。3.Reference108. 多余的边KamaCoder109.多余的边II109. 多余的边II1.思路这个图最初是一棵有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; vectorintfather(1005,1); void init(){ for(int i1;in;i){ father[i]i; } } int find(int u){ if(ufather[u]){ return u; } return father[u]find(father[u]); } bool issame(int u,int v){ ufind(u); vfind(v); return uv; } void join(int u,int v){ ufind(u); vfind(v); if(uv) return; father[u]v; } // 删一条边之后判断是不是树 bool isdelete(vectorpairint,intedges,int u){ init(); for(int i1;in;i){ if(iu) continue; if(issame(edges[i].first,edges[i].second)){ // 构成有向环了一定不是树 return false; } else join(edges[i].first,edges[i].second); } return true; } int main(){ cinn; vectorpairint,intedges(n1); // 存边 vectorintindegree(n1,0); // 记录节点入度 for(int i1;in;i){ int s,t;cinst; edges[i]{s,t}; indegree[t]; } vectorintvec; // 找入度为2的节点所对应的边 for(int i1;in;i){ if(indegree[edges[i].second]2){ vec.push_back(i); } } if(vec.size()0){ // 优先删vec[1] 对应这条边 if(isdelete(edges,vec[1])){ coutedges[vec[1]].first edges[vec[1]].secondendl; } else coutedges[vec[0]].first edges[vec[0]].secondendl; return 0; } // 明确没有入度为2的情况那么一定有有向环找到构成环的边返回就可以了 // 在有向图里找到删除的那条边使其变成树 init(); for(int i1;in;i){ if(issame(edges[i].first,edges[i].second)){ coutedges[i].first edges[i].secondendl; return 0; } else join(edges[i].first,edges[i].second); } return 0; }2.思考这道题较上道题难度天差地别。有多余的边我们就要讨论几种情况第一种就是有入度为 2 的节点那么显而易见该节点相关的两条边中的一条就是冗余的边那么此时我们就假设删除第二条边然后看剩余边能否构成有向树如果能那么该条边就是冗余的否则第一条边就是冗余的还有一种情况就不存在入度为 2 的节点但此时还是存在冗余边所以就是形成了环此时也就来到了 多余的边 那道题的情况只需要依次连接节点遇到在同一集合的两节点立即输出返回此时两节点构成的边即为多余的边。3.Reference109. 冗余连接II | 代码随想录