斯巴达

用户名：AcmeGaga

访问量：1974

签　名：

等　　级
排　　名	5424
经　　验	1544
参赛次数	0
文章发表	22
年　　龄	0
在职情况	学生
学　　校	河南大学
专　　业

　　自我简介：

TA的其他文章

1575 递归倒置字符数组 java
浏览：136

1907: 蓝桥杯算法提高VIP-递推求值 java
浏览：498

1917: 蓝桥杯算法提高VIP-快乐司机
浏览：138

你可能喜欢

A+B for Input-Output Practice (III) （C++代码）

A+B for Input-Output Practice (VII) （C语言代码）

1744: 畅通工程代码搬运工(java)

　　作者: 斯巴达　　　　发表时间：2022-03-12 20:27:02 浏览：152　|　评论：0　

原题链接：畅通工程

- 思路
    
    [并查集详解（C++代码）（小白向）-Dotcpp编程社区](https://blog.dotcpp.com/a/76623)
    
    本题无思路, 直接分析别人的代码
    
    借用并查集思想, 有步骤如下:
    
    - 循环输入路径, 合并路径左右的**树**
    - 遍历整个并查集, 查看有多少个根节点, 输出 `根节点数 -1`
- 代码
    
    ```java
    import java.util.*;
    public class Main {
    	public static void main(String[] args) {
    		int x, y, n, m;
    		Scanner scan = new Scanner(System.in);
    		while(scan.hasNext()) {
			//这个while不要省略, 否则会卡到test 50
    			n = scan.nextInt();
    			if(n==0) break;
    			m =scan.nextInt();
    			disJiontSet parent = new disJiontSet();
    			parent.parent = new int[n+1];
    			parent.disJointSet();
    			
    			for(int i=1; i<=m ;i++) {
    				x = scan.nextInt();
    				y = scan.nextInt();
    				parent.unite(x, y);
    			}
    			int cnt = 0;
    			for(int i=1; i<=n; i++) {
    				if(parent.parent[i] == i)
    					cnt++;
    			}
    			System.out.println(cnt-1);
    		}
    	}
    	static class disJiontSet{
    		int parent[];
    		void disJointSet() {
    			for(int i=0; i<parent.length; i++){
    				parent[i] = i;
    			}
    		}
    		
    		int find(int x) {
    			if(parent[x] == x)
    				return x;
    			else 
    				return parent[x] = find(parent[x]);
    		}
    		
    		boolean unite(int x, int y) {
    			int rootX = find(x);
    			int rootY = find(y);
    			if(rootX == rootY) {
    				return false;
    			}
    			parent[rootY] = rootX;
    			return true;
    		}
    	}
    }
    ```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

斯巴达

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

printf基础练习2 （C语言代码）

A+B for Input-Output Practice (III) （C++代码）

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

A+B for Input-Output Practice (VII) （C语言代码）

1744: 畅通工程代码搬运工(java)

评论区

精彩推荐

【明明的随机数】（C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

C语言程序设计教程（第三版）课后习题8.9 （C++代码）（其实不需要开数组，一个一个字符读入并判断就好了）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

【蟠桃记】（C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

Cylinder （C语言描述+详细分析）

C语言训练-亲密数（C语言描述,反正怎么都能对）

斯巴达

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

printf基础练习2 （C语言代码）

A+B for Input-Output Practice (III) （C++代码）

产生数 （C++代码）（大数乘法也是可以避免的么hhhh）

A+B for Input-Output Practice (VII) （C语言代码）

1744: 畅通工程 代码搬运工(java)

评论区

精彩推荐

【明明的随机数】 （C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

C语言程序设计教程（第三版）课后习题8.9 （C++代码）（其实不需要开数组，一个一个字符读入并判断就好了）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

【蟠桃记】 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

Cylinder （C语言描述+详细分析）

C语言训练-亲密数 （C语言描述,反正怎么都能对）

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

1744: 畅通工程代码搬运工(java)

　　评论区

【明明的随机数】（C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

【蟠桃记】（C语言代码）

C语言训练-亲密数（C语言描述,反正怎么都能对）