Code Practice Journal | Day 56

Code Practice Journal | Day 56_Graph06

本文主要是介绍Code Practice Journal | Day 56_Graph06，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

KamaCoder 107. 寻找存在的路径

题目：107. 寻找存在的路径 (kamacoder.com)
题解：代码随想录 (programmercarl.com)

solution

class Program
{public static void Main(string[] args){string[] dimensions = Console.ReadLine().Split();int n = int.Parse(dimensions[0]);int m = int.Parse(dimensions[1]);DSU dsu = new DSU(n);for (int i = 0; i < m; i++){string[] nums = Console.ReadLine().Split();int x = int.Parse(nums[0]) - 1;int y = int.Parse(nums[1]) - 1;dsu.union(x, y);}string[] nodes = Console.ReadLine().Split();Console.WriteLine(dsu.find(int.Parse(nodes[0]) - 1) == dsu.find(int.Parse(nodes[1]) - 1) ? 1 : 0);}
}class DSU
{int[] dsu;public DSU(int size){dsu= new int[size];for (int i = 0; i < size; i++){dns[i] = i;}}public int find(int num){if (dsu[num] != num){dsu[num] = find(dsu[num]);}return dsu[num];}public void union(int x, int y){int rootx = find(x);int rooty = find(y);if (rootx != rooty){dsu[rootx] = y;}}
}

KamaCoder 108. 冗余连接

题目：108. 冗余连接 (kamacoder.com)
题解：代码随想录 (programmercarl.com)

solution

class Program
{public static void Main(string[] args){int num1 = 0;int num2 = 0;string N = Console.ReadLine();int n = int.Parse(N);DSU dsu = new DSU(n);for (int i = 0; i < n; i++){string[] nums = Console.ReadLine().Split();int x = int.Parse(nums[0]) - 1;int y = int.Parse(nums[1]) - 1;if (dsu.union(x, y)){num1 = x;num2 = y;}}Console.WriteLine(string.Join(" ", num1 + 1, num2 + 1));}
}class DSU
{int[] dsu;public DSU(int size){dsu = new int[size];for (int i = 0; i < size; i++){dsu[i] = i;}}public int find(int num){if (dsu[num] != num){dsu[num] = find(dsu[num]);}return dsu[num];}public bool union(int x, int y){int rootx = find(x);int rooty = find(y);if (rootx != rooty){dsu[rootx] = y;return false;}else return true;}
}

summary

key：

（成环）删除的边：构成边的两个节点具有相同的根

改造union函数：遇到需要删除的边则记录节点，否则将边加入并查集

KamaCoder 107. 冗余连接Ⅱ

题目：109. 冗余连接II (kamacoder.com)
题解：代码随想录 (programmercarl.com)

solution

class Program
{public static void Main(string[] args){//处理输入//  维度string N = Console.ReadLine();int n = int.Parse(N);// 数组int[][] edges = new int[n + 1][];for (int i = 1; i <= n; i++){string[] nodes = Console.ReadLine().Split();edges[i][0] = int.Parse(nodes[0]);edges[i][1] = int.Parse(nodes[1]);}//初始化// 可能的双父节点int[] candi1 = null;int[] candi2 = null;// dsu数组DSU dsu = new DSU(n + 1);//检查双父节点并拆分foreach (int[] edge in edges){int parent = edge[0];int child = edge[1];if (dsu.dsu[child] != child){// 原边candi1 = new int[] { dsu.dsu[child], child };// 新边candi2 = new int[] { parent, child };// 拆分edge[1] = 0;}else{dsu.dsu[child] = parent;}}//检查环// 重新初始化for (int i = 0; i <= n; i++){dsu.dsu[i] = i;}foreach (int[] edge in edges){if (edge[1] == 0) continue;int parent = edge[0];int child = edge[1];if (!dsu.union(parent, child)){if (candi1 == null){Console.WriteLine($"{parent} {child}");}else{Console.WriteLine($"{candi1[0]} {candi2[1]}");}return;}}Console.WriteLine($"{candi2[0]} {candi2[1]}");}
}public class DSU
{public int[] dsu;public DSU(int size){dsu = new int[size];for (int i = 0; i < size; i++){dsu[i] = i;}}public int find(int num){if (dsu[num] != num){dsu[num] = find(dsu[num]);}return dsu[num];}public bool union(int x, int y){int rootx = find(x);int rooty = find(y);if (rootx == rooty) return false;else{dsu[y] = x;return true;}}
}