代码随想录算法训练营第五十四天|108.冗余连接、109.冗余连接II

题目链接108.冗余连接解题思路并查集具体思路首先定义全局变量 n 和长度为 1001 的父节点数组 father实现并查集核心函数find 带路径压缩的查找找到节点根节点并进行路径压缩降低查找耗时、init 初始化 0 到 n 的节点父节点为自身保证初始时每个节点独立成集、join 合并两个节点所在集合先查找两节点根节点若不同则将 v 的根节点父节点指向 u 的根节点、isSame 判断两节点是否同根即是否连通主函数中先读取边的数量 n调用 init 初始化父节点数组再循环 n 次读取每条边的两个端点 s 和 t先调用 isSame 判断 s 和 t 是否连通若连通则输出该边的 s 和 t说明这条边构成环若未连通则调用 join 合并 s 和 t 所在的集合。具体代码#includeiostream #includevector using namespace std; int n; vectorint father(1001, 0); int find (int u) { if (u father[u]) return u; else return father[u] find(father[u]); } void init() { for (int i 0; i n; i) father[i] i; } void join(int u, int v) { u find(u); v find(v); if (u v) return; else father[v] u; } bool isSame (int u, int v) { u find(u); v find(v); if (u v) return true; else return false; } int main () { cin n; init(); for (int i 0; i n; i) { int s; int t; cin s t; if(isSame(s, t)) cout s t endl; else join(s, t); } }题目链接109.冗余连接II解题思路并查集具体思路首先实现并查集核心函数 find 带路径压缩找根节点、init 初始化父节点、join 合并集合、isSame 判断节点连通性定义辅助函数 isTreeAfterRemoveEdge验证删除指定索引的边后剩余边能否构成无环连通的树遍历除删除边外的所有边若合并时发现节点已连通则有环返回 false否则返回 true定义辅助函数 getRemoveEdge遍历所有边用并查集找到第一条使节点连通的成环边并输出主函数中先读取 n统计每个节点入度 inDegree、存储所有边首先统计每个节点的入度筛选出入度为 2 的节点对应的边并逆序记录其索引若存在这类边调用 isTreeAfterRemoveEdge 先尝试移除第一条该类边通过并查集验证移除后图是否满足树的条件所有节点连通且无环满足则输出该边否则输出第二条入度为 2 的边若不存在入度为 2 的边则调用 getRemoveEdge 直接遍历所有边利用并查集找到第一条导致环的边即两个节点已连通时试图合并的边该边即为需移除的边。具体代码#includeiostream #includevector using namespace std; int n; vectorint father(1001, 0); int find (int u) { if (u father[u]) return u; else return father[u] find(father[u]); } void init() { for (int i 0; i n; i) father[i] i; } void join(int u, int v) { u find(u); v find(v); if (u v) return; else father[v] u; } bool isSame (int u, int v) { u find(u); v find(v); if (u v) return true; else return false; } bool isTreeAfterRemoveEdge(vectorvectorint edges, int deleteIndex) { init(); for (int i 0; i n; i) { if(i deleteIndex) continue; int u edges[i][0]; int v edges[i][1]; if (isSame(u, v)) return false; join(u, v); } return true; } void getRemoveEdge(vectorvectorint edges) { init(); for (int i 0; i n; i) { int u edges[i][0]; int v edges[i][1]; if (isSame(u, v)) { cout u v; return; } else { join(u, v); } } } int main () { cin n; vectorint inDegree(n 1, 0); vectorvectorint edges; for (int i 0; i n; i) { int s; int t; cin s t; inDegree[t]; edges.push_back({s, t}); } vectorint inDegree2; for (int i n - 1; i 0; i--) { if (inDegree[edges[i][1]] 2) inDegree2.push_back(i); } if (inDegree2.size() 0) { if (isTreeAfterRemoveEdge(edges, inDegree2[0])) { cout edges[inDegree2[0]][0] edges[inDegree2[0]][1]; } else { cout edges[inDegree2[1]][0] edges[inDegree2[1]][1]; } return 0; } getRemoveEdge(edges); }