海贼OJ并查集练习题:朋友圈

﹏ヽ暗。殇╰゛Y 2023-03-13 03:55 318阅读 0赞

## 海贼OJ并查集练习题:朋友圈 ##

**题目描述**

所谓一个朋友圈子，不一定其中的人都互相直接认识。

**例如**：小张的朋友是小李，小李的朋友是小王，那么他们三个人属于一个朋友圈。

现在给出一些人的朋友关系，人按照从 1 到 n 编号在这中间会进行询问某两个人是否属于一个朋友圈，请你编写程序，实现这个过程。

**输入**

第一行输入两个整数 n,m(1≤n≤10000，3≤m≤100000)，分别代表人数和操作数。

接下来 m 行，每行三个整 a,b,c（a∈\[1,2\], 1≤b,c≤n）  
当 a=1时，代表新增一条已知信息，b,c 是朋友  
当 a=2 时，代表根据以上信息，询问 b,c 是否是朋友  
**输出**

对于每个 a=2 的操作，输出『Yes』或『No』代表询问的两个人是否是朋友关系。

**样例输入**

6 5  
1 1 2  
2 1 3  
1 2 4  
1 4 3  
2 1 3  
**样例输出**

No  
Yes

**思路**：并查集的简单应用，无需多言，上代码

#include<iostream> 
    using namespace std;
    
    int n;
    int Father[10001];
    
    int find(int x) { 
    	if (Father[x] == x) return x;
    	else return Father[x] = find(Father[x]);
    }   //查找根结点
    
    int main() { 
    	int m;
    	cin >> n >> m;
    	for (int i = 1; i <= n; i++) Father[i] = i;
    	while (m--) { 
    		int a, b, c;
    		cin >> a >> b >> c;
    		if (a == 1) Father[find(c)] = find(b);   //合并
    		if (a == 2) { 
    			if (find(b) == find(c)) cout << "Yes\n";
    			else cout << "NO\n";
    		}
    	}
    	return 0;
    }
    //声明Father数组时如果使用动态数组int * Father=new int[n+1];或者int<vector>Father(n+1);会超时

发表评论取消回复

表情：

评论列表（有 0 条评论，318人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode547朋友圈，使用并查集和图的搜索

1、使用并查集 class DisjoinSet{ private: vector<int>_id; //元素对应的集合，根

缺乏、安全感/ 2023年06月03日 14:52/ 0 赞/ 2 阅读

相关海贼OJ并查集练习题:朋友圈

海贼OJ并查集练习题:朋友圈题目描述所谓一个朋友圈子，不一定其中的人都互相直接认识。例如：小张的朋友是小李，小李的朋友是小王，那么他们三个人属于一个朋友

﹏ヽ暗。殇╰゛Y/ 2023年03月13日 03:55/ 0 赞/ 319 阅读

相关 leetcode 547. 朋友圈 dfs | 并查集

dfs 每次拿到一个没有访问的节点就dfs一遍把它和它的朋友都标记了最后看看dfs了几次就有几个朋友圈 class Solution { p

╰+哭是因爲堅強的太久メ/ 2022年12月12日 04:53/ 0 赞/ 141 阅读

相关【leetcode.547】朋友圈(形象生动讲解并查集)

本文转载自[Union-Find 算法详解][Union-Find] 今天讲讲 Union-Find 算法，也就是常说的并查集算法，主要是解决图论中「动态连通性」问题的。名词

r囧r小猫/ 2022年12月11日 04:24/ 0 赞/ 129 阅读

相关【数据结构】并查集：LeetCode题 547.朋友圈问题

[547. 朋友圈][547.] 班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以

川长思鸟来/ 2022年11月03日 00:48/ 0 赞/ 162 阅读

相关朋友圈

1、题目描述班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C

雨点打透心脏的1/2处/ 2022年10月01日 06:47/ 0 赞/ 216 阅读

相关圈内朋友

[C++圈内人][C] http://jjhou.boolan.com/ 侯捷 http://blog.csdn.net/myan 孟岩 http://blog.c

你的名字/ 2022年08月06日 09:18/ 0 赞/ 266 阅读

相关【九度OJ】:1526 并查集朋友圈问题

假如已知有n个人和m对好友关系（存于数字r）。如果两个人是直接或间接的好友（好友的好友的好友…），则认为他们属于同一个朋友圈，请写程序求出这n个人里一共有多少个朋友圈。

灰太狼/ 2022年07月21日 01:56/ 0 赞/ 134 阅读

相关天梯赛朋友圈（并查集）

Problem Description: 某学校有N个学生，形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好，形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。

我会带着你远行/ 2022年02月25日 04:20/ 0 赞/ 234 阅读

相关【影评】海贼王：855

大半年没有看海贼王了，作为一个老海迷惭愧啊！还是在蛋糕岛篇！ 855：主要还是路飞和卡二的战斗，作为10亿贝利的卡二，见闻色简直完美，果实能力也和路飞差不多，听说还是个

本是古典何须时尚/ 2021年12月07日 11:25/ 0 赞/ 220 阅读