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日 1900点热度 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
取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
上岸 Star Divine 现代前端工程师发展方向不完全指北 站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话
先有华为后有天,不买华为是汉奸 恭喜四叶小天使取得最后的胜利 动态规划(DP)方法学习 WPscan扫描Wordpress漏洞的工具使用教程 #动漫#路人女主的养成方法第二季 1080P 中国银行莫奈卡万事达借记卡网申与评测
标签聚合
C++ 动漫 C/C++ 日常 ST HTML 洛谷 OI
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

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

Theme Kratos Made By Seaton Jiang