APTX博客

  • ACGN
  • Coding
  • DevOps
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By ミズキ
  1. 首页
  2. OI
  3. 正文

#洛谷#C/C++P3367并查集的使用及其实现

2018年4月30日 1283点热度 0人点赞 0条评论

性质

并查集算法(union_find sets)支持分割一个集合,求连通子图、求最小生成树(克鲁斯卡尔)

输入输出格式

输入格式:

第一行包含两个整数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 2 3
2 1 4

输出样例#1:
N
Y
N
Y

模板代码

#include <iostream>
#include <cstdio>
using namespace std;

int fa[10005],n,m;
int find(int);

int main(){
	scanf ("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        fa[i]=i;
    for(int i=0;i<m;++i){
        int ask,x,y;
        scanf ("%d%d%d",&ask,&x,&y);
        if (ask==1) fa[find(x)]=find(y);
        else 
            if (find(x)==find(y))
                printf ("Y\n");
            else printf ("N\n");
    }
    return 0;
}
int find(int x){ //并查集核心
	if(x==fa[x]) return x;
	else return fa[x]=find(fa[x]);
}

 

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: C/C++ C++ 图论 并查集 洛谷
最后更新:2018年4月30日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版
MMPI(明尼苏达多相人格问卷)临床量表 情色漫画老师OVA两话2160P 《从零》第二季&《春物》第三季制作决定 WPscan扫描Wordpress漏洞的工具使用教程 #笔记#二进制与位运算 开源项目Python网易云音乐歌曲批量下载
标签聚合
C/C++ 日常 ST OI C++ 动漫 洛谷 HTML
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

COPYRIGHT © 2017-2022 APTX博客. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang