并查集-一笔画优化

╰+哭是因爲堅強的太久メ 2022-07-12 12:15 132阅读 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 条评论，132人围观）

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

相关阅读

相关并查集 size 的优化

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

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

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

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

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

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

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

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

相关【贪心+并查集优化】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 赞/ 92 阅读

相关查并集及优化

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

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

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

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

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

相关并查集-一笔画

package 搜索.并查集; import java.util.Scanner; /\ \ 先用并查集，判断图是否连通， \ 然后在利用欧拉图的特

àì夳堔傛蜴生んèń/ 2022年07月12日 12:15/ 0 赞/ 123 阅读

相关并查集-一笔画优化

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

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

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

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

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

相关数据结构（十一）并查集的实现和优化

并查集 1. 数组存储的基础实现此时并查集用一个结构体存储，data 存值（下标+1），parent 存父结点下标查找操作中先线性查找到需要找到的值，再循环

灰太狼/ 2022年04月18日 03:18/ 0 赞/ 20 阅读