题目描述

简单的并查集模板

输入描述

第一行包含两个整数N、M，表示共有N个元素和M个操作。

接下来M行，每行包含三个整数Zi、Xi、Yi

当Zi=1时，将Xi与Yi所在的集合合并

当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N。

分析

简单的模板，解释留到算法微解读

AC代码

#include <bits/stdc++.h>

using namespace std;

int n,m;

int fa[10000+5];

inline int read(){

	int X=0,w=0; char ch;

	while (!isdigit(ch)) {w|=ch=='0'; ch=getchar();}

	while (isdigit(ch)) {X=(X<<3)+(X<<1)+(ch^48);ch=getchar();}

	return w?-X:X;

}

int gf(int x) {

	if (fa[x]==x) return fa[x];

	else return fa[x]=gf(fa[x]);

}

int main()

{

	n=read(),m=read();

	for (int i=1;i<=n;i++) fa[i]=i;

	while (m--) {

		int x=read(),y=read(),z=read(),p1=gf(y),p2=gf(z);

		if (x==2) {

			if (p1==p2) printf("Y\n");

			else printf("N\n");

		}

		else if (p1!=p2) fa[p1]=p2;

	}

	return 0;

}

巴特西

【并查集模板】并查集模板 luogu-3367

题目描述

输入描述

分析

AC代码

最新文章

热门文章