洛谷 P3367 并查集模板

#include<cstdio>
using namespace std;
int n,m,p;
int father[2000001];
int find(int x)
{
    if(father[x]!=x)
        father[x]=find(father[x]);
    return father[x];
}
void unionn(int i,int j)
{
    father[j]=i;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        father[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x,y,z,r1,r2;
        scanf("%d%d%d",&z,&x,&y);
        if(z==1)
        {
            r1=find(x);
            r2=find(y);
            if(r1!=r2)
                unionn(r1,r2);
        }
        if(z==2)
        {
            if(find(x)==find(y))
                printf("Y\n");
            else    printf("N\n");
        }
    }

    return 0;
}

洛谷的网站编排对题目粘贴不友好,所以没题目

链接在这:https://www.luogu.org/problem/show?pid=3367

时间: 04-10

洛谷 P3367 并查集模板的相关文章

洛谷p3367 并查集模板

并查集是一种树型的数据结构,主要用来处理一些不相交集合的合并和更改问题. 比如找4的祖先,原来是 4->2->1,通过并查集路径压缩后,变为 4->1.也就变成了下图. 并查集的模板题: #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m; int dad[2000001]; int find(int x)//很简单的find函数,网上还

并查集模板

//普通并查集模板 #include<iostream> using namespace std; const int MAX=10004; int fat[MAX];//存放每个节点的根节点 //找x的根节点并且把路径上的每个节点的父节点改成根节点 int find(int x) //while找根节点 { int rt=x; while(fat[rt]!=rt) rt=fat[rt]; int i=x,j; while(i!=rt){ j=fat[i]; fat[i]=rt; i=j; }

并查集 模板

const int MAX=1010;  //元素个数的最大值,根据题目修改int p[MAX];void init(int n) //n为实有元素个数{    for (int i=1; i<=n; i++)  p[i]=i;  }int find(int x) //查找{   if (x==p[x]) return x;    else  return  p[x]=find(p[x]);} void merge(int x,int y) //合并{   int px,py;    px=fi

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

题目描述 简单的并查集模板 输入描述 第一行包含两个整数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

洛谷P3367 【模板】并查集

P3367 [模板]并查集 293通过 551提交 题目提供者HansBug 标签 难度普及- 提交  讨论  题解 最新讨论 不知道哪错了 为啥通不过最后三个节点 题解 不懂为什么MLE 最后一个数据? 题目描述 如题,现在有一个并查集,你需要完成合并和查询操作. 输入输出格式 输入格式: 第一行包含两个整数N.M,表示共有N个元素和M个操作. 接下来M行,每行包含三个整数Zi.Xi.Yi 当Zi=1时,将Xi与Yi所在的集合合并 当Zi=2时,输出Xi与Yi是否在同一集合内,是的话输出Y:否

洛谷 P3367 【模板】并查集

题目描述 如题,现在有一个并查集,你需要完成合并和查询操作. 输入输出格式 输入格式: 第一行包含两个整数N.M,表示共有N个元素和M个操作. 接下来M行,每行包含三个整数Zi.Xi.Yi 当Zi=1时,将Xi与Yi所在的集合合并 当Zi=2时,输出Xi与Yi是否在同一集合内,是的话输出Y:否则话输出N 输出格式: 如上,对于每一个Zi=2的操作,都有一行输出,每行包含一个大写字母,为Y或者N 输入输出样例 输入样例#1: 4 7 2 1 2 1 1 2 2 1 2 1 3 4 2 1 4 1

并查集模板、

并查集是一种用来管理元素分组情况的数据结构. 并查集的复杂度:并查集加入两个优化(路径压缩和高度的合并)以后效率很高,对n个元素的并查集进行一次操作的复杂度是O(a(n)).在这里,a(n)是阿克曼(Ackermann)函数的反函数,这比O(log(n))还快,不过这是“均摊复杂度”,也就是说不是每一次操作都满足这个复杂度,而是多次操作以后平均每一次的操作的复杂度是O(a(n)) 1 int par[MAX_N]; //父亲 2 int rank[MAX_N]; //树的高度 3 4 //初始化

【总结】并查集模板

并查集是解决集合之间关系的一种很好理解的数据结构 就相当于将一个个集合合并成一棵树 然后将每个节点都只想根节点 主要两个操作是join(a,b);将两个节点合并在一起 find(x);查找x的根节点 时间复杂度为树的高度O(h) 如果数据特别没节操就会卡成一条链 就成O(n)的时间复杂度了 优化有两种方法 其中路径压缩是最常见的 因为树的形态完全不重要 所以将树的节点都连在同一层上 时间复杂度就成O(1)了; 给一个介绍很形象生动的博客http://blog.csdn.net/ljfbest/a

PAT甲题题解-1114. Family Property (25)-(并查集模板题)

题意:给出每个人的家庭成员信息和自己的房产个数与房产总面积,让你统计出每个家庭的人口数.人均房产个数和人均房产面积.第一行输出家庭个数,随后每行输出家庭成员的最小编号.家庭人口数.人均房产个数.人均房产面积. 并查集,合并的时候编号小的作为父亲节点,最后父亲节点一样的即属于一个家庭,其它都是细节处理没啥好说了. #include <iostream> #include <cstdio> #include <algorithm> #include <string.h