洛谷P3367-【模板】并查集(并查集模板题)

简介: 洛谷P3367-【模板】并查集(并查集模板题)

题目描述:


如题,现在有一个并查集,你需要完成合并和查询操作。


输入:



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

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

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

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


输出:


如上,对于每一个Zi=2的操作,都有一行输出,每行包含一个大写字母,为Y或者N


样例输入:


4 7

2 1 2

1 1 2

2 1 2

1 3 4

2 1 4

1 2 3

2 1 4


样例输出:


N

Y

N

Y


说明/提示:


时空限制:1000ms,128M

数据规模:

对于30%的数据,N<=10,M<=20;

对于70%的数据,N<=100,M<=1000;

对于100%的数据,N<=10000,M<=200000。


程序代码:


#include<bits/stdc++.h>
using namespace std;
int i,j,k,n,m,p1,p2,p3;
int f[10001];
int getf(int v)
{
  if(f[v]==v)
    return v;
  else
  {
    f[v]=getf(f[v]);
    return f[v];
  }
}
void merge(int v,int u)
{
  int t1=getf(v);
  int t2=getf(u);
  if(t1!=t2)
    f[t2]=t1;
}
int main()
{
  cin>>n>>m;
  for(i=1;i<=n;i++)
    f[i]=i;
  for(i=1;i<=m;i++)
  {
    cin>>p1>>p2>>p3;
    if(p1==1)
      merge(p2,p3);
    else
    {
      if(getf(p2)==getf(p3))
        cout<<"Y"<<endl;
      else
        cout<<"N"<<endl;
    }
  }
  return 0;
}
相关文章
|
5月前
【洛谷 P2089】烤鸡(深度优先搜索)
## 摘要: 猪猪Hanke的烤鸡问题要求找出所有配料组合,使得$10$种配料(每种$1$到$3$克)的总和等于给定美味程度$n$。输入为正整数$n$,输出为方案总数及所有符合条件的配料分配,按字典序排列。样例输入$11$,输出$10$种方案。代码采用递归搜索,先计数再打印方案。$n\leq5000$时保证数据覆盖。
30 0
|
5月前
【洛谷 P1443】马的遍历 题解(广度优先搜索)
该问题是一个棋盘上的马的最短路径问题。给定一个$n\times m$的棋盘和起点$(x, y)$,需要计算马到达棋盘上每个位置的最短步数。输入包含$n, m, x, y$,输出是一个矩阵,表示各位置的步数或未可达的$-1$。使用广度优先搜索(BFS)策略,从起点开始遍历,直到访问完所有可达位置。代码中定义了太阳数组表示马的移动方向,并通过队列实现BFS。最后输出格式要求每个数字左对齐且域宽为5。
39 0
|
6月前
|
算法 C++
一题带你写出图论算法模板!!!
一题带你写出图论算法模板!!!
|
机器学习/深度学习 存储 C++
[蓝桥杯] 树状数组与线段树问题(C/C++)
[蓝桥杯] 树状数组与线段树问题(C/C++)
79 0
|
算法
并查集模板题
并查集模板题
48 0
|
算法
数星星(树状数组模板题)
数星星(树状数组模板题)
59 0
Trie树,并查集的简单应用(AcWing)
Trie树,并查集的简单应用(AcWing)
76 0
《蓝桥杯每日一题》递归·AcWing 1497. 树的遍历
《蓝桥杯每日一题》递归·AcWing 1497. 树的遍历
60 0
|
算法
算法 - 蓝桥杯并查集题型
算法 - 蓝桥杯并查集题型
洛谷P1443 马的遍历——广搜
洛谷P1443 马的遍历——广搜
76 0