并查集-一笔画优化

╰+哭是因爲堅強的太久メ 2022-07-12 12:15 163阅读 0赞

package 搜索.并查集;  
import java.util.Scanner;  
  
  
/\*  
\* 1:使用num算出总的合并次数。  
\* 5个点，最少要保证合并5-1次才能保证图连通  
\* num<n-1;不连通  
\* num+1<n  
\* n-num>1  
\*/  
public class 一笔画优化 \{  
static int\[\] pre;  
  
  
public static void main(String\[\] args) \{  
Scanner sc = new Scanner(System.in);  
int n = sc.nextInt();  
while (n-- > 0) \{  
int p = sc.nextInt();  
int q = sc.nextInt();  
pre = new int\[p + 1\];  
int arr\[\] = new int\[p + 1\];  
for (int i = 1; i <= p; i++)  
pre\[i\] = i;  
int a, b;  
int num = 0;// 优化1  
for (int i = 0; i < q; i++) \{  
a = sc.nextInt();  
b = sc.nextInt();  
arr\[a\]++;  
arr\[b\]++;  
int x = find(a);  
int y = find(b);  
if (x != y) \{  
pre\[x\] = y;  
num++;  
\}  
\}  
  
  
if (p - num > 1)  
System.out.println("No");  
else \{  
num = 0;  
for (int i = 1; i <= p; i++) \{  
if (num > 2)// 优化2  
break;  
num += (arr\[i\] % 2);  
\}  
if (num == 0 || num == 2) \{  
System.out.println("Yes");  
\} else \{  
System.out.println("No");  
\}  
\}  
\}  
\}  
  
  
private static int find(int a) \{//优化3  
if (a == pre\[a\])  
return a;  
return pre\[a\] = find(pre\[a\]);  
\}  
  
  
\}

发表评论取消回复

表情：

评论列表（有 0 条评论，163人围观）

还没有评论，来说两句吧...

相关阅读

相关并查集 rank 的优化

上一小节介绍了并查集基于 size 的优化，但是某些场景下，也会存在某些问题，如下图所示，操作 union(4,2)。 ![71cc2c79c55c2c77840a35588

Dear 丶/ 2024年03月16日 23:48/ 0 赞/ 38 阅读

相关并查集 size 的优化

按照上一小节的思路，我们把如下图所示的并查集，进行 union(4,9) 操作。 ![a3da8b269ba354b7ed0a63675bd6dbc9.png][] 合并操

傷城~/ 2024年03月16日 23:18/ 0 赞/ 58 阅读

相关 nyoj 42 一笔画问题（欧拉通路+dfs || 并查集）

一笔画问题时间限制： 3000 ms | 内存限制： 65535 KB 难度： 4 描述 zyc从小就比较喜欢玩一些小游戏，其中就包括画一笔画，他想请你帮他写一个

Love The Way You Lie/ 2024年02月17日 20:21/ 0 赞/ 44 阅读

相关并查集 size 的优化（并查集 size 的优化）

目录并查集 size 的优化 Java 实例代码 UnionFind3.java 文件代码： -------------------- 并查集 size 的优化

痛定思痛。/ 2023年10月14日 21:07/ 0 赞/ 46 阅读

相关并查集，不就一并和一查？

什么是并查集并查集这种数据结构，可能出现的频率不是那么高，但是还会经常性的见到，其理解学习起来非常容易，通过本文，一定能够轻轻松松搞定并查集！对于一种数据结构，肯定

谁借莪１个温暖的怀抱￠/ 2023年01月17日 08:00/ 0 赞/ 115 阅读

相关【贪心+并查集优化】Supermarket

A supermarket has a set Prod of products on sale. It earns a profit px for each product

客官°小女子只卖身不卖艺/ 2022年11月14日 00:45/ 0 赞/ 135 阅读

相关查并集及优化

基础对于今天要总结的算法，我想先通过一道题目来看一下：假设现在我有一个任务交给你：要求你查看 id 为 x 和 id 为 y 的两个人是不是朋友，

清疚/ 2022年09月28日 01:20/ 0 赞/ 155 阅读

相关一笔画问题（并查集+无向欧拉图）

一笔画问题时间限制： 3000 ms | 内存限制： 65535 KB 难度： 4 描述 zyc从小就比较喜欢玩一些小游戏，其中就包括画一笔画，他想请你帮他写

待我称王封你为后i/ 2022年08月02日 05:45/ 0 赞/ 183 阅读

相关并查集-一笔画优化

package 搜索.并查集; import java.util.Scanner; /\ \ 1:使用num算出总的合并次数。 \ 5个点，最少要保

╰+哭是因爲堅強的太久メ/ 2022年07月12日 12:15/ 0 赞/ 164 阅读

相关并查集NYOJ—一笔画问题

一笔画问题时间限制： 3000 ms | 内存限制： 65535 KB 难度： 4 描述 zyc从小就比较喜欢玩一些小游戏，其中就包括画一笔画，他想请你帮他写

电玩女神/ 2022年06月01日 12:48/ 0 赞/ 167 阅读