当前位置:网站首页>Blue bridge: sympodial plant
Blue bridge: sympodial plant
2022-07-04 18:11:00 【A Bai|】
Problem description
w A plantation on the planet , Is divided into m * n A little lattice ( East west direction m That's ok , North South n Column ). There's a sympodial plant in each grid .
This plant has a characteristic , Its roots may extend north-south or East-West , So that it can be integrated with another lattice of plants .
If we tell you which cells are rooted , Can you tell me how many sympodial plants there are in this garden ?Input format
first line , Two integers m,n, Separate with spaces , Represents the number of rows in the grid 、 Number of columns (1<m,n<1000).
Next line , An integer k, It means that there are more k Row data (0<k<100000)
Next k That's ok , The first 2+k Line two integers a,b, Indicates that the number is a And the number is b My little lattice is rooted .The number of the grid line by line , From top to bottom , Number from left to right .
such as :5 * 4 The little lattice of , Number :
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20The sample input
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17Sample explanation : See the figure below for the root combination ( Be careful :6 It is also a connected subset )
Sample output
5
Union checking set
Code :
package p1.text; import java.util.*; /** * @author WitMoy * @version V1.8 * @date : 2022-07-02 18:16 */ public class Main { private static final Scanner sc = new Scanner(System.in); private static int place[] = new int[1005]; private static int rank[] = new int[1005]; public static void main(String[] args) { int m, n, k; m = sc.nextInt(); n = sc.nextInt(); k = sc.nextInt(); int ans = 0; init(m * n); for(int i = 0; i < k; i++){ int a = sc.nextInt(); int b = sc.nextInt(); join(a,b); } HashSet<Integer> hs = new HashSet<>(); for(int i = 1; i < n * m; i++){ hs.add(place[i]); } System.out.println(hs.size()); } private static void init(int n){ for(int i = 1; i <= n; i++){ place[i] = i; rank[i] = 1; } } private static int find(int x){ if(place[x] == x) return x; return place[x] = find(place[x]); } private static void join(int x, int y){ x = find(x); y = find(y); if(x == y) return; if(rank[x] > rank[y]){ place[y] = x; }else{ if(rank[x] == rank[y]) rank[y]++; place[x] = y; } } }
边栏推荐
- Five thousand words to clarify team self-organization construction | Liga wonderful talk
- With an estimated value of 90billion, the IPO of super chip is coming
- MySQL常用增删改查操作(CRUD)
- Cocoscreator event dispatch use
- 超标量处理器设计 姚永斌 第6章 指令解码 摘录
- Superscalar processor design yaoyongbin Chapter 7 register rename excerpt
- Once the "king of color TV", he sold pork before delisting
- Rainfall warning broadcast automatic data platform bwii broadcast warning monitor
- Oppo Xiaobu launched Obert, a large pre training model, and promoted to the top of kgclue
- Superscalar processor design yaoyongbin Chapter 5 instruction set excerpt
猜你喜欢
Easy to use map visualization
解读数据安全治理能力评估框架2.0,第四批DSG评估征集中
创业两年,一家小VC的自我反思
Offline and open source version of notation -- comprehensive evaluation of note taking software anytype
The controversial line of energy replenishment: will fast charging lead to reunification?
蓝桥:合根植物
超标量处理器设计 姚永斌 第6章 指令解码 摘录
MySQL常用增删改查操作(CRUD)
CocosCreator事件派發使用
Cann operator: using iterators to efficiently realize tensor data cutting and blocking processing
随机推荐
2022 national CMMI certification subsidy policy | Changxu consulting
Introduction of time related knowledge in kernel
Mathematical analysis_ Notes_ Chapter 7: differential calculus of multivariate functions
解读数据安全治理能力评估框架2.0,第四批DSG评估征集中
明星开店,退,退,退
ISO27001 certification process and 2022 subsidy policy summary
With an estimated value of 90billion, the IPO of super chip is coming
爬虫初级学习
2022年DCMM认证全国各地补贴政策汇总
【210】PHP 定界符的用法
12 - explore the underlying principles of IOS | runtime [isa details, class structure, method cache | t]
大厂面试总结大全二
Flask 轻量web框架
Solve the El input input box For number number input problem, this method can also be used to replace the problem of removing the arrow after type= "number"
Load test practice of pingcode performance test
简单易用的地图可视化
Performance test of Gatling
7 RSA Cryptosystem
Cann operator: using iterators to efficiently realize tensor data cutting and blocking processing
Summary of subsidy policies across the country for dcmm certification in 2022