搜索结果
查询Tags标签： 查集，共有 135条记录-
leetcode(c++)(并查集)
#include <iostream> #include <vector>using namespace std;class DSU{public:vector<int>parent;DSU(int n){parent = vector<int>(n);for(int i = 0; i< n; ++i){parent[i] = i;} }int Find(int x){if(parent[x] != x)parent[x] = F…
2022/5/3 22:13:09 人评论 次浏览 -
并查集的高级应用
1 给定一个 nm 的矩阵，其中 q 个位置已经被填充。 2 有一条规则，如果 (r1,c1)(r1,c1) ，(r1,c2)(r1,c2)，(r2,c1)(r2,c1) 均被填充，则 (r2,c2)(r2,c2) 也被填充。任何被其他三个位置生成的位置，也可以继续生成其他位置。问最少需要再人为填充多少元素，使矩阵被填满。…
2022/5/1 23:12:54 人评论 次浏览 -
399. 除法求值(并查集)
399. 除法求值给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。 另有一些以数组 queries 表示的问题，其中 queries[j] …
2022/4/29 23:12:35 人评论 次浏览 -
NOI2015 洛谷P1955 程序自动分析（并查集+离散化）
这可能是我目前做过的最简单的一道noi题目了...... 先对e=1的处理，用并查集；再对e=0查询，如果这两个在同一集合中，则为“”NO“，最后都满足的话输出”“YES”； 数值很大，用一下离散化就行了。1 #include<bits/stdc++.h>2 using namespace std;3 const int N=…
2022/4/16 17:12:39 人评论 次浏览 -
并查集
并查集 说明并查集是一种精巧使用的数据结构，主要用于处理一些不相交的集合合并问题。经典的例子有连通子图、最小生成树Kruskal算法和LCA等。原理将编号分别为1~n个对象分为不相交的集合，每个集合中，选择其中某个元素代表所在的集合。在这个集合中，并查集的操作有初始…
2022/4/3 23:24:07 人评论 次浏览 -
并查集
#include <iostream>using namespace std;const int N = 100010;int p[N];int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x]; }int main() {int n, m;scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ ) p[i] = i;while (m…
2022/3/27 6:23:01 人评论 次浏览 -
国王的烦恼 蓝桥算法真题 并查集 java实现
package qs;/** * 测试数据为： 4 4 1 2 2 1 3 2 2 3 1 3 4 3* * * */import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.Scanner;public class testunionfind {static int s[];// static Bridge[] b=new Bridge…
2022/3/19 1:28:07 人评论 次浏览 -
leetcode之并查集+记忆化搜索+回溯+最小生成树刷题总结1
leetcode之并查集+记忆化搜索+回溯+最小生成树刷题总结1 1-连接所有点的最小费用 题目连接：题目连接戳这里！！！ 思路:cruskal+并查集 根据题意，我们得到了一张 n 个节点的完全图，任意两点之间的距离均为它们的曼哈顿距离。现在我们需要在这个图中取得一个子图，恰满足…
2022/2/28 23:26:52 人评论 次浏览 -
Leetcode 261. 以图判树（中等） 1135. 最低成本联通所有城市（中等） 1584. 连接所有点的最小费用（中等） 并查集&Kruskal最小生成树
思路讲解 261. 以图判树（中等） 题目： 给定编号从 0 到 n - 1 的 n 个结点。给定一个整数 n 和一个 edges 列表，其中 edges[i] = [ai, bi] 表示图中节点 ai 和 bi 之间存在一条无向边。 如果这些边能够形成一个合法有效的树结构，则返回 true ，否则返回 false 。 示例…
2022/2/22 23:47:16 人评论 次浏览 -
【算法基础课模板笔记+注释】 数据结构11 --- 并查集
声明 本文资料参考acwing算法基础课 地址：https://www.acwing.com 概述 解决问题：并查集这里并查集用下标代表元素 模板记忆 这个模板分为四个部分： 初始化：并查集用一个数组即可，表示父节点，根节点指向自己并：把两个集合合并成一个，使用递归 模板代码 int p[N]; …
2022/2/20 11:26:34 人评论 次浏览 -
2022/2/17 思考。
其实是 Solution Set. 「GXOI / GZOI2019」旅行者 显然考虑超源超汇一类东西。要找到一些染色方法使得所有 \(\forall (u,v),u \neq v,c_u = 1,c_v = 0\) 都被包含。 这个可以说是典中典，枚举二进制下每一位是 \(1\) 还是 \(0\)，第一次是 \(1\) 的位置的点连源点，第二次…
2022/2/17 23:14:42 人评论 次浏览 -
c/c++的小知识点：并查集
在朋友圈、旅游线路等问题中均使用到并查集的概念，在数据结构中讲过这个知识点 相关题目： 1.旅行路线规划 PTA | 程序设计类实验辅助教学平台 2.朋友圈 PTA | 程序设计类实验辅助教学平台 并查集有两个基本操作 1.find：查找元素所属子集 2.union：合并两个子集为一个新…
2022/2/5 17:12:45 人评论 次浏览 -
leecode 765 情侣牵手问题，并查集+问题转换能力
分析：假设有 N对情侣，假设有 K 个集合（存在情侣的集合），（偶数，偶数+1）为一个元素最少的集合这种情况符合题意不需要交换。假设每个集合里面有 m1，m2, m3.......mk个元素，需要进行m1-1，m2-1, m3-1.......mk-1次交换，求和得到本题答案为N - K class UnionSet:de…
2022/2/3 6:14:34 人评论 次浏览 -
【带权并查集 + DP】真正的骗子
这题属实逆天。。题面在输出格式中没有说明需要将编号排序后输出，让我困惑了半天呜呜。 分析 题目本身的思路是很简单的。 我们从一个人说 yes 和 no 能够得到什么呢？假设这个人是天神，那么说 yes 说明对方也是天神，否则是恶魔。 假设这个人是恶魔，那么说 yes 说明对…
2022/2/1 23:10:11 人评论 次浏览 -
LeetCode力扣839.相似字符串组(C++)【并查集】详细解析+代码注释
LeetCode力扣839.相似字符串组 题目描述 如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。 给你多个字符串。每个字符串都是其他所有字符串的一个字母异位词。请问给出…
2022/1/29 1:04:55 人评论 次浏览
