loj#109.并查集

关键词：

3 6
1 1 0
0 0 1
1 0 1
1 1 2
0 2 1
1 2 1

5

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int MAXN=8000001;
 7 const int mod=998244353;
 8 inline void read(int &n)
 9 {
10     char c=‘+‘;bool flag=0;n=0;
11     while(c<‘0‘||c>‘9‘) c==‘-‘?flag=1,c=getchar():c=getchar();
12     while(c>=‘0‘&&c<=‘9‘) n=n*10+c-48,c=getchar();
13 }
14 int fa[MAXN];
15 int size[MAXN];
16 int n,m;
17 string p;
18 int find(int x)
19 {return fa[x]==x?fa[x]:fa[x]=find(fa[x]);}
20 int query(int x,int y)
21 {return find(x)==find(y);}
22 void unionn(int x,int y)
23 {
24     int fx=find(x);int fy=find(y);
25     if(fx!=fy)
26     {
27         if(size[fx]>size[fy])    swap(fx,fy);
28         fa[fx]=fy;    size[fy]+=size[fx];
29         //fa[fx]=fy;
30     }
31 }
32 int ans=0;
33 int main()
34 {
35     //freopen("a.in","r",stdin);
36     //freopen("a.out","w",stdout);
37     read(n);read(m);
38     for(int i=1;i<=n;i++)    fa[i]=i;
39     for(int i=1;i<=m;i++)
40     {
41         int how;read(how);
42         if(how)// 询问 
43         {
44             int x,y;read(x);read(y);
45             ans=(ans*2+query(x,y))%mod;
46         }
47         else//连边 
48         {
49             int x,y;read(x);read(y);
50             unionn(x,y);
51         }
52     }
53     printf("%d",ans);
54     return 0;
55 }

loj6157a^bproblem(并查集)

...常不好处理这里考虑维护一个点到其根的路径的异或值用并查集去检测m个测试若s和t不在一个并查集内：　　挑出s的根f1，t的根f2，father[f1]=f2，并且发现w[f1]=c^w[s]^w[t]若s和t在一个并查集内：　　那么首先这个并查集内的所有点... 查看详情

loj6198谢特后缀数组+并查集+trie

先把问题放在后缀数组上考虑已知两个数组ab，求min(a[i],...,a[j])+(b[i]^b[j])的最大值套路题初始每个点都是一个小连通块把a按从大到小的顺序加入，计算当前加入边作为min的贡献：每次加入会把两个连通块联通，答案就是两边连通... 查看详情

libreoj#109.并查集(代码片段)

内存限制：256MiB时间限制：2000ms标准输入输出题目类型：传统评测方式：文本比较上传者：匿名【题目描述】这是一道模板题。维护一个nnn点的无向图，支持：加入一条连接uuu和vvv的无向边查询uuu和vvv的连通性由于本题数据较大... 查看详情

[loj3246]cavepaintings(代码片段)

...个状态，容易想到一个思路：从下往上进行枚举，用一个并查集维护这一行的所有点，然后将这一行与下一行相邻的点连起来，形成这一行的并查集通过并查集，可以将同一行内在同一个并查集内的点缩起来，并向下面的点连边... 查看详情

[loj6038]远行

用合并直径的定理，并查集维护每棵树的直径主要是看看过了这么久自己的lct有没有变残废2333（1A还行#include<stdio.h>intch[300010][2],fa[300010],r[300010],siz[300010],sfa[300010],d1[300010],d2[300010];voidpushup(intx){siz[x]=siz[ch[x][0]]+siz[ 查看详情

❤️数据结构入门❤️（2-5）-并查集

文章目录一、并查集的定义二、并查集的图解三、并查集的实现1、并查集的插入2、并查集的删除3、并查集的修改4、并查集的查找四、并查集的刷题实战一、并查集的定义二、并查集的图解三、并查集的实现1、并查集的插入2、... 查看详情

并查集

并查集1.并查集是什么并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作。不过需要注意并查集虽然可以进行合并操作，但是无法进行分割操作。查询元素a和元素b是否属于同一组。合并元素a和元... 查看详情

并查集

并查集--basicpublicclassUnionFind1{privateint[]parent;//数组,表示并查集所有元素的集合号privateintsize;//表示并查集元素个数publicUnionFind1(intsize){//并查集初始化this.size=size;parent=newint[size];for(inti=0;i<size;i++){parent[i]= 查看详情

并查集并查集

模板数组版：intparent[MAX_N];intrank[MAX_N];voidInit(intn){ for(inti=0;i<n;++i){ parent[i]=i; rank[i]=0; }}intFind(intx){ if(parent[x]=x){ returnx; }else{ returnFind(parent[x]); }}voidUnion(intx,inty 查看详情

并查集-----好忧伤的并查集

 主要还是看find的join俩个操作,测试数据16124313566171#include<iostream>#include<stdio.h>#include<memory.h>usingnamespacestd;/***并查集判断有几个联通子图*/constintmaxN=20;inta[maxN];intfind(intkey);voidjoi 查看详情

数据结构----并查集(代码片段)

并查集并查集概念并查集的模拟实现模拟实现并查集优化Union优化压缩路径循环递归并查集例题并查集概念并查集在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集... 查看详情

并查集学习笔记

并查集是用来查询、合并的有力工具。并查集是用来查询、合并的有力工具。 查看详情

并查集

...立的元素通过某种方式相互合并为若干个集合的方法即为并查集。 intset[N];//并查集集合for(i=0;i<=N;i++)set[i]=i;//并查集初始化，每个元素自为一个集合intfind(inti){//并查集查找，某个元素为根代表这个集合intr=i;while(r!=set[r])r=set... 查看详情

并查集p3367模板并查集(代码片段)

P3367【模板】并查集#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>usingnamespacestd;intn,m,zi,xi,yi;intfather[10001] 查看详情

并查集原理分析(代码片段)

文章目录1.并查集是什么2.并查集性质3.并查集可以解决的问题4.并查集模板5.并查集的应用1.并查集是什么在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时**，每个元素自成一个单元素集合**࿰... 查看详情

数据结构--并查集(代码片段)

并查集并查集原理并查集实现并查集原理在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要... 查看详情

并查集——新手学习记录(代码片段)

好吧，什么垃圾并查集，并查集什么的都是铁憨憨<+__+>现在开始复习回忆：（新手，有错误望指正）什么叫做并查集，并查集就是一个集合问题，其实最主要的就是知道并查集是一个求解集合数目的问题，具体的操作方法有... 查看详情

数据结构----并查集(代码片段)

并查集并查集概念并查集的模拟实现模拟实现并查集优化Union优化压缩路径循环递归(深度过深有栈溢出的风险)并查集例题并查集概念并查集在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每... 查看详情