专业的高端企业网站,能免费建网站吗,公司免费建网站,西部数码 网站管理第56天#xff0c;图论06#xff0c;并查集题目类型冗余连接(ง •_•)ง#x1f4aa;#xff0c;编程语言#xff1a;C
目录
108.冗余连接
109.冗余连接II
总结 108.冗余连接 文档讲解#xff1a;手撕冗余连接 题目#xff1a;108. 冗余连接 (kamacoder.com) 学习图论06并查集题目类型冗余连接(ง •_•)ง编程语言C
目录
108.冗余连接
109.冗余连接II
总结 108.冗余连接 文档讲解手撕冗余连接 题目108. 冗余连接 (kamacoder.com) 学习本题也可以用并查集的方法进行求解。原因在于要使得删除一条边后图变为一棵树也即只有一个根节点。
只有一个根节点也就意味着大家都在一个集合之中。因此我们可以采取从前向后遍历的顺序遍历每一条边边的两个节点如果不再同一个集合就加入集合。
如果在同一个集合那就说明这条边的两个节点已经连通了加入这条边一定会出现环则需要将这条边删除。并且事实上在我们发现这条边的时候就已经是我们找到的答案中的最后出现的边了因为我们是从前往后遍历的遍历到这条边就已经是必须要删除的状态了
代码先写出并查集模板然后进行求解
#include iostream
#include vector
using namespace std;//并查集模版
int n;
vectorint father(n 1, 0); //节点从1开始因此我们定义一个n1大小的数组void init() { //初始化father数组for(int i 0; i n; i) {father[i] i;}
}int find(int u) { //寻根函数// return u father ? u : father[u] find(father[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[v] u;
}int main() {cin n;init(); //初始化数组int s, t;for (int i 0; i n; i) { //进行并查集合并cin s t;if (isSame(s, t)) {cout s t endl;return 0;} else {join(s, t);}}return 0;
} 109.冗余连接II 文档讲解手撕冗余连接II 题目109. 冗余连接II (kamacoder.com) 学习本题是将无向图转变为有向图相对的会复杂一些。但我们需要明确本题中的有向图指的是一颗有向树一条有向边组成的。同时有向树的特点在于只有根节点的入度为0其他节点入度都为1。
基于此我们可以考虑两种情况第一种情况有一个节点的入度为2第二种情况存在环即没有入度为0的根节点
第一种情况又可以分为两种情形
1.如果我们找到入度为2的点那么删除一条指向该节点的边就行。以下图为例删1 - 3 或者 2 - 3都可以选择删除顺序靠后便可。 2.入度为2也有另一种情况只能删除特定的一条边。以下图为例只能删除边1-3另一条边是不可以删除的会丢失一个点。 第二种情况没有入度为2的点而是存在环。以下图为例删除构成环的边使得到一个入度为0的根节点即可。 分析好了以上三种情形之后我们就可以针对性的进行代码的书写。
针对第一种情况我们可以统计每个节点的度找寻是否有节点度为2的节点。 int s, t;vectorvectorint edges;cin n;vectorint inDegree(n 1, 0); // 记录节点入度for (int i 0; i n; i) {cin s t;inDegree[t];edges.push_back({s, t});}如果有的话一定是删除指向入度为2的节点的两条边其中的一条如果删了一条判断这个图是一个树则这条边就是答案同时我们还要保证是从前往后遍历的以便于我们删除最后一条边
vectorint vec; // 记录入度为2的边如果有的话就两条边
// 找入度为2的节点所对应的边注意要倒序因为优先删除最后出现的一条边
for (int i n - 1; i 0; i--) {if (inDegree[edges[i][1]] 2) {vec.push_back(i);}
}
if (vec.size() 0) {// 放在vec里的边已经按照倒叙放的所以这里就优先删vec[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;
}
而对于第二种情况也就是出现环的情况则我们按照上一题的办法找到成环的边即可。
// 在有向图里找到删除的那条边使其变成树
void getRemoveEdge(const vectorvectorint edges)
接下来我们就是要实现 isTreeAfterRemoveEdge()和getRemoveEdge()这两个函数了。
第一个函数用于判断删除一个边之后是不是有向树方法是通过将所有边的两端节点加入并查集遇到要删除的边则跳过只有删除了正确的边才能够将所有节点都加入并查集。否则会出现丢失点并且另外的点成环的情况。
第二个函数则是确定了有环则我们只需要将所有边的两端节点加入并查集并且从前往后直到遇到第一个使得并查集出现重复的边则说明这条边是要删除的边。
由此可以看出这两个函数的实现其实都可以是在上一题基础上进行实现的。
代码在并查集的基础上加入两函数
#include iostream
#include vector
using namespace std;//并查集模版
int n;
vectorint father(1001, 0); //节点从1开始因此我们定义一个n1大小的数组void init() { //初始化father数组for(int i 0; i n; i) {father[i] i;}
}int find(int u) { //寻根函数// return u father ? u : father[u] find(father[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[v] u;
}// 删一条边之后判断是不是树
bool isTreeAfterRemoveEdge(const vectorvectorint edges, int deleteEdge) {init(); // 初始化并查集for (int i 0; i n; i) {if (i deleteEdge) continue; //跳过删除的边if (isSame(edges[i][0], edges[i][1])) { // 构成有向环了一定不是树return false;}join(edges[i][0], edges[i][1]);}return true;
}// 在有向图里找到删除的那条边使其变成树
void getRemoveEdge(const vectorvectorint edges) {init(); // 初始化并查集for (int i 0; i n; i) { // 遍历所有的边if (isSame(edges[i][0], edges[i][1])) { // 构成有向环了就是要删除的边cout edges[i][0] edges[i][1];return;} else {join(edges[i][0], edges[i][1]);}}
}int main() {cin n;int s, t;vectorvectorint edges; //保存边vectorint inDegree(n 1, 0); // 记录节点入度for (int i 0; i n; i) {cin s t;inDegree[t]; //t是入度edges.push_back({s, t});}vectorint vec; // 记录入度为2的边如果有的话就两条边// 找入度为2的节点所对应的边注意要倒序因为优先删除最后出现的一条边for (int i n - 1; i 0; i--) { //从后往前保证边是倒叙进入的以便于输出最后一条边if (inDegree[edges[i][1]] 2) {vec.push_back(i); //把边的序号加入}}// 第一种情况if (vec.size() 0) {// 放在vec里的边已经按照倒叙放的所以这里就优先删vec[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);return 0;
} 总结
今天的两道题是对并查集的巩固考察。第二道题增加了对有向图的分析但实际上还是使用了并查集具备的查找两个元素是否在一个集合查找成环的能力。需要多加练习
