关键词：
1.了解了各种输入挂性orz，找到了一个合适的
2.find用while写能快一倍，并且能被数据卡掉
3.取模只能快十几毫秒，但也能被数据卡掉
取模find双优化是1997mm过的
再加一个性价比较高的输入挂是438mm 23333
#include <cstdio> #include <cmath> #include <complex> #include <algorithm> #include <iostream> #include<string.h> #include<vector> #include<ctime> #define rep(i,t,n) for(int i =(t);i<=(n);++i) #define per(i,n,t) for(int i =(n);i>=(t);--i) #define mmm(a,b) memset(a,b,sizeof(a)) typedef long long ll; using namespace std; #define N 2333333 const ll M= 998244353; const int maxn = 4e6 + 5; int f[maxn]; using namespace std; template<typename T>inline void add_(T &A, int B, ll MOD = M) A += B; (A >= MOD) && (A -= MOD); template<typename T>inline void mul_(T &A, ll B, ll MOD = M) A = (A*B) % MOD; namespace IO const int MAXL = 1 << 15; char buf[MAXL], *S, *T, ch; inline char Getch() if (S == T) T = (S = buf) + fread(buf, 1, MAXL, stdin); return S == T ? EOF : *S++; inline void Read(int &x) x = 0; while (!isdigit(ch = Getch())); do x = x * 10 + (ch ^ ‘0‘); while (isdigit(ch = Getch())); using namespace IO; int find(int x) while (f[x] ^ x)x = f[x] = f[f[x]]; return x; void un(int x, int y) int xx = find(x), yy = find(y); if(xx^yy)f[xx] = yy; int main() int n, m; cin >> n >> m; rep(i, 1, n)f[i] = i; int op, a, b; ll ans = 0; rep(i, 1, m) Read(op); Read(a); Read(b); if(!op)un(a, b); else add_(ans, ans + (find(a) == find(b))); cout << ans << endl; cin >> n;
libreoj#109.并查集
二次联通门:LibreOJ#109.并查集 /*LibreOJ#109.并查集并查集*/#include<cstdio>#defineMax4000090#defineMod998244353voidread(int&now){now=0;registercharword=getchar();while(word<‘0‘||w 查看详情
模板：并查集
1//递归版路径压缩2intfind(intx){returnx==Father[x]?x:Father[x]=find(Father[x]);}34voidUnion(intx,inty){5intfx=find(x),fy=find(y);6if(fx!=fy)Father[fx]=fy;7}//合并 查看详情
并查集模板(代码片段)
并查集1.合并两个集合2.查询两个数是否在一个集合基本原理：每个集合用一棵树来表示，树根的编号就是整个集合的编号，每个结点存储他的父节点，p[x]表示x的父节点1.是否是一个集合if(find(a)==find(b))2.合并两个集合 p[find(a)... 查看详情
并查集模板
#include<cstdio>#include<iostream>usingnamespacestd;intf[1001];intx,y;intm,n,q,i;intfind(intx){if(f[x]!=x)f[x]=find(f[x]);returnf[x];}voidhb(intx,inty){inta=find(x);intb=find(y);if(a!=b)f[ 查看详情
yangk's并查集-模板(代码片段)
//并查集-都要给fa赋初值！！//======================================/*递归版路径压缩*/intfa[maxn];intfind(intx)returnfa[x]==x?x:fa[x]=find(fa[x]);voidmerge(intx,inty)fa[find(x)]=find(y);//=========================== 查看详情
并查集模板(代码片段)
voidinit()for(inti=1;i<=maxx;i++)pre[i]=i;//初始化intFind(intx)returnpre[x]==x?x:(pre[x]=Find(pre[x]));//状态压缩+找最上面的祖先voidjoin(intx,inty)fx=Find(x);fy=Find(y);if(fx!=fy)pre[fx]=fy;//加入合并 查看详情
常规并查集模板(代码片段)
常规并查集模板#defineMaxsize100+1intf[Maxsize];voidinit(intn)for(inti=1;i<=n;i++)f[i]=i;intfind_f(inta)if(f[a]==a)returna;elsereturnf[a]=find_f(f[a]);voidunion_f(inta,intb)intaf=find_f(a);intbf=f 查看详情
并查集(模板)
1intp[MAX];//父亲2intrank[MAX];//树的高度34//初始化n个元素5intinit(intn)6{7for(inti=0;i<n;i++){8p[i]=i;9rank[i]=0;10}11}1213//查询树的根14intfind(intx)15{16if(p[x]==x)17returnx;18else19returnp[x]=find(p[x]);20}2122 查看详情
并查集模板
传送门：亲戚 1#include<cstdio>23constintMAXN=10001;45intFather[MAXN],n,m;6charCheck[3]={‘N‘,‘Y‘};78intFind(intt)9{10if(t!=Father[t])returnFather[t]=Find(Father[t]);11returnFather[t];12}1314voidUn 查看详情
并查集模板
1#include<iostream>2#include<cstdio>3#include<cstring>4#include<algorithm>5usingnamespacestd;67intN,M,fa[10005];8intfind(int);910voidpt(intx,inty)11{12intfaa=find(x);13intfbb=f 查看详情
p3367模板并查集
P3367【模板】并查集#include<bits/stdc++.h>usingnamespacestd;constintN=1e4+10;inta[N];intn,m;intfa[N];intfind(intx) if(fa[x]==x) returnx; fa[x]=find(fa[x]); returnfa[x];intmain() scanf("%d%d",&am 查看详情
并查集的模板写法(代码片段)
1并查集:2#include<utility>3#include<iostream>4#include<set>5#include<map>6#include<vector>7#include<queue>8#include<cmath>9#include<algorithm>10constintMAX_E=10001;11constintMAX_N=10000;12constintINF=999999;13usingnamespacestd;14//先搞并查集:15... 查看详情
并查集（模板）
题目描述如题，现在有一个并查集，你需要完成合并和查询操作。输入输出格式输入格式：第一行包含两个整数N、M，表示共有N个元素和M个操作。接下来M行，每行包含三个整数Zi、Xi、Yi当Zi=1时，将Xi与Yi所在的集合合并当Zi=2时... 查看详情
并查集模板
intfind(intx)//寻找x的根 inti=x,j; while(root[x]!=x)//如果x的根节点不为他本身则继续找 x=root[x]; while(i!=x)//路径压缩 j=root[i]; root[i]=x; i=j; returnx;voidUnion(intx,inty)//合并x，y成一个集合inta=find(x);//x的根节点为aintb 查看详情
并查集模板（算法）(代码片段)
并查集是由一个数组pre[]，和两个函数构成的，一个函数为find()函数，用于寻找前导点的，第二个函数是combine()用于合并路线的1intfindx(intx)23inta;4a=x;5while(pre[a]!=a)///循环方法查找任意一个城市的前导点67a=pre[a];89/*if(pre[x]!=x)///递归... 查看详情
洛谷p3367-并查集（java模板）(代码片段)
并查集概论加权标记法总结P3367并查集P1551亲戚概论定义：并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。比如，我们可以用并查集来判断一个森林中有几棵树... 查看详情
洛谷p3367并查集模板
#include<cstdio>usingnamespacestd;intn,m,p;intfather[2000001];intfind(intx){if(father[x]!=x)father[x]=find(father[x]);returnfather[x];}voidunionn(inti,intj){father[j]=i;}intmain(){scanf("%d%d",& 查看详情
并查集模板(代码片段)
constintN=120;intfather[N];intrank1[N];voidinit(intSize)for(inti=1;i<=Size;++i)father[i]=i,rank1[i]=0;intFind(intx)while(x!=father[x])x=father[x];returnx;boolUnion(intx,inty)intfx,fy;fx=Find(x),fy=Find(y);if(fx==fy)returnfalse;elseif(rank1[fx]>=rank1[fy])father[fy]=fx;rank1[fx]+=rank1[fy];else... 查看详情