关键词：
- 内存限制：256 MiB
- 时间限制：2000 ms
- 标准输入输出
- 题目类型：传统
- 评测方式：文本比较
上传者： 匿名
【题目描述】
这是一道模板题。
维护一个 nnn 点的无向图，支持：
加入一条连接 uuu 和 vvv 的无向边
查询 uuu 和 vvv 的连通性
由于本题数据较大，因此输出的时候采用特殊的输出方式：用 000 或 111 代表每个询问的答案，将每个询问的答案依次从左到右排列，把得到的串视为一个二进制数，输出这个二进制数 mod 998244353 extmod ~ 998244353mod 998244353 的值。
【输入格式】
第一行包含两个整数 n,mn,mn,m，表示点的个数和操作的数目。
接下来 mmm 行每行包括三个整数 op,u,v extop,u,vop,u,v。
如果 op=0 extop = 0op=0，则表示加入一条连接 uuu 和 vvv 的无向边；
如果 op=1 extop = 1op=1，则表示查询 uuu 和 vvv 的连通性。
【输出格式】
一行包括一个整数表示答案。
样例
- 样例输入
3 6
1 1 0
0 0 1
1 0 1
1 1 2
0 2 1
1 2 1
- 样例输出
5
- 样例解释
答案串为 0101。
【数据范围与提示】
n≤4000000,m≤8000000n≤4000000,m≤8000000n≤4000000,m≤8000000
By zyz
AC代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
const int inf = 998244353;
int fa[4000010],size[4000010],bin[8000010],n,m,ans;
int readint() //读入优化
int Num;
char ch;
while((ch=getchar())<'0'||ch>'9');
Num=ch-'0';
while((ch=getchar())>='0'&&ch<='9')
Num=Num*10+ch-'0';
return Num;
int equal(int x,int y) //判断是否相等
if(x==y) return 1;
else return 0;
int get(int x)
if(fa[x]==x)return x;
else return fa[x] = get(fa[x]); //路径压缩
void merge(int a,int b) //合并两个集合
int aa,bb;
aa=get(a);
bb=get(b);
if(aa!=bb)
//这里很重要！！！
if(size[aa]>=size[bb]) //将子节点少的集合合并到子节点多的集合，省时间
fa[aa]=bb;
size[aa] += size[bb];
else
fa[bb]=aa;
size[bb] += size[aa];
int main()
int op,u,v;
n=readint();
m=readint();
for(int i=0;i<n;i++) fa[i]=i; //一开始每个点都为一个集合，父节点是自己
for(int i=1;i<=m;i++)
op=readint();
u=readint();
v=readint();
if(op==0) merge(u,v);
else
ans = (ans*2 + equal(get(u),get(v)))%inf; //这里直接用get(u)==get(v)测试时出错，所以写了个int型的函数判断
//当然也可以用if判断，ans++
cout<<ans%inf;
return 0;
libreoj模板并查集（输入挂，取模与find优化）(代码片段)
1.了解了各种输入挂性orz，找到了一个合适的 2.find用while写能快一倍，并且能被数据卡掉3.取模只能快十几毫秒，但也能被数据卡掉取模find双优化是1997mm过的 再加一个性价比较高的输入挂是438mm 23333#include<cstdio>#in... 查看详情
loj#109.并查集
内存限制：256MiB时间限制：2000ms标准输入输出题目类型：传统评测方式：文本比较上传者：匿名提交提交记录统计讨论1测试数据 题目描述这是一道模板题。维护一个 nnn 点的无向图，支持：加入一条连接 uuu ... 查看详情
并查集(代码片段)
主要内容本文主要记录并查集的基本实现方法，并逐步将一些例题填充到文章中。并查集能做什么并查集可以：1.合并集合2.查找两个元素是否在同一个集合内3.集合数量4.确定元素属于哪个集合。完整代码示例classUFpublic:UF();UF(int... 查看详情
markdown并查集(代码片段)
golang并查集(代码片段)
并查集p3367模板并查集(代码片段)
P3367【模板】并查集#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>usingnamespacestd;intn,m,zi,xi,yi;intfather[10001] 查看详情
数据结构----并查集(代码片段)
并查集并查集概念并查集的模拟实现模拟实现并查集优化Union优化压缩路径循环递归并查集例题并查集概念并查集在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集... 查看详情
并查集——新手学习记录(代码片段)
好吧，什么垃圾并查集，并查集什么的都是铁憨憨<+__+>现在开始复习回忆：（新手，有错误望指正）什么叫做并查集，并查集就是一个集合问题，其实最主要的就是知道并查集是一个求解集合数目的问题，具体的操作方法有... 查看详情
并查集原理分析(代码片段)
文章目录1.并查集是什么2.并查集性质3.并查集可以解决的问题4.并查集模板5.并查集的应用1.并查集是什么在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时**，每个元素自成一个单元素集合**... 查看详情
数据结构--并查集(代码片段)
并查集并查集原理并查集实现并查集原理在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要... 查看详情
关于并查集的一切全在这里了(代码片段)
文章目录并查集初识「并查集」常用术语「并查集」基本思想「并查集」的两个实现方式QuickFind方式实现并查集QuickFind工作原理：代码实现与验证时间复杂度QuickUnion方式实现并查集QuickUnion的工作原理为什么QuickUnion比QuickFind... 查看详情
数据结构----并查集(代码片段)
并查集并查集概念并查集的模拟实现模拟实现并查集优化Union优化压缩路径循环递归(深度过深有栈溢出的风险)并查集例题并查集概念并查集在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每... 查看详情
并查集(代码片段)
本文参考了【算法】并查集（DisjointSet）和并查集详解并查集原理并查集是一种用于处理不相交集合之间合并问题的数据结构，例如求连通子图、判断是否存在环、求最小生成树等。以判断图中是否有环为例，下图是一个无向图... 查看详情
dzyloveschemistry（并查集）(代码片段)
题目：（??，最近净做并查集了还一道难的都不会）DZYloveschemistry,andheenjoysmixingchemicals.DZYhasnchemicals,andmpairsofthemwillreact.Hewantstopourthesechemicalsintoatesttube,andheneedstopourtheminonebyone,inanyorder.Let‘sc 查看详情
树的应用——并查集及实现代码(代码片段)
文章目录什么是并查集亲戚问题并查集的实现改进——路径压缩进一步改进——合并并查集的用途什么是并查集 并查集是一种树型的数据结构，用于处理一些不相交集合（disjointsets）的合并及查询问题。常常在使用... 查看详情
并查集(入门)(代码片段)
首先先看一道很简单的并查集的题目：https://vjudge.net/contest/297398#problem/A这道题就是让你判断两两城镇之间是否联通 如果不联通就要修建一条道路 就我的理解来说，如果单独使用并查集就是为了合并有相同根结点(或者理... 查看详情
并查集(代码片段)
/*并查集*/#include<stdio.h>int*a;int*sz;intcount;//thenumberofconnectedcomponent//uniontwoconnectedcomponentswithweightsvoidunion_two_points(intp,intq)inti=root(p);intj=root(q);if(i==j)return;if(s 查看详情
并查集(代码片段)
...们看两道题 亲戚 朋友 显然我们需要并查集。 So,什么是并查集？ 并，就是合并关系（也就是认祖宗）。查，就是查找关系（就是看祖宗是不是一个人）。集，是因为它是个集合。 并查集怎么写呢... 查看详情