首页 > 其他分享 >擒贼先擒王(并查集)

擒贼先擒王(并查集)

时间:2023-07-23 15:45:17浏览次数:49  
标签:int 查集 样例 强盗 擒贼先擒王 同伙

擒贼先擒王(并查集)

目录

题面

快过年了,犯罪分子也开始为年终奖奋斗了。晓哼的家乡出现了多次抢劫事件。由于强盗人数过于庞大,作案频繁,警方想查清楚到底有几个犯罪团伙实在太不容易了,不过警察叔叔还是搜集到了一些线索,需要咱们帮忙分析一下:
现在有10个强盗。
1号强盗与2号强盗是同伙。
3号强盗与4号强盗是同伙。
5号强盗与2号强盗是同伙。
4号强盗与6号强盗是同伙。
2号强盗与6号强盗是同伙。
8号强盗与7号强盗是同伙。
9号强盗与7号强盗是同伙。
1号强盗与6号强盗是同伙。
2号强盗与4号强盗是同伙。
有一点需要注意,强盗同伙的同伙也是同伙。你能帮助警方查出有多少个独立的犯罪团伙吗?

输入
第一行n m,n(n< 3000 )表示强盗的人数,m表示警方搜集到的m(m< 5000 )条线索。

接下来的m行每一行有两个数 a b。表示强盗a和强盗b是同伙。

输出
有多少个独立的犯罪团伙

样例
样例输入1

10 9
1 2
3 4
5 2
4 6
2 6
8 7
9 7
1 6
2 4

样例输出1

3

题目概括

我们要找出所有数据,依照题目关系条件,可以组成的树的棵数

思路

并查集不清楚的朋友看这儿
先按照输入建树,再统计有多少个结点的上级是它本身(根节点)
最后把它A掉

AC代码和注释

#include<bits/stdc++.h>
using namespace std;
int n,m;
int parent[5005];
void init(int n) {//初始化 
    for(int i = 1;i <= n;i ++) {
        parent[i] = i;
    }
}
int find(int t){//查找 
	if(parent[t] == t) return t;
	else return parent[t] = find(parent[t]);
}
void merge(int r1,int r2){//合并 
	parent[find(r2)] = find(r1);
}
int main(){
	cin >> n >> m;
	init(n);
	for(int i = 1;i <= m;i ++){
		int x,y;
		cin >> x >> y;
		merge(x,y);
	}
	int ans = 0;
	for(int i = 1;i <= n;i ++){//记录有多少个结点的上级是它本身(根节点)
		if(parent[i] == i) ans ++;
	}
	cout << ans;
	return 0;
}

标签:int,查集,样例,强盗,擒贼先擒王,同伙
From: https://www.cnblogs.com/L-1115/p/17574649.html

相关文章

  • 并查集知识梳理
    并查集目录并查集并查集的定义并查集的思想朴素并查集的代码(1)初始化(2)查找(3)合并路径压缩(1)查找代码(2)路径压缩完整代码按秩合并思想实现(1)初始化(2)合并并查集的定义并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题。并查集通常包含两种操作:查找(Find):查询两个......
  • 并查集知识点梳理
    并查集目录并查集并查集的定义并查集的思想朴素并查集的代码(1)初始化(2)查找(3)合并路径压缩(1)查找代码(2)路径压缩完整代码按秩合并思想实现(1)初始化(2)合并并查集的定义并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题。并查集通常包含两种操作:查找(Find):查询两个......
  • java 检查集合长度
    Java检查集合长度的实现方法概述在Java开发中,我们经常需要检查集合的长度,以便判断集合中是否包含足够的元素或者进行其他操作。本文将介绍一个简单的方法来实现Java检查集合长度的功能。实现步骤下面是实现Java检查集合长度的步骤,可以用表格形式展示:步骤描述......
  • 并查集
    题目一共有$n$个数,编号是$1∼n$,最开始每个数各自在一个集合中。现在要进行$m$个操作,操作共有两种:Mab,将编号为$a$和$b$的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作;Qab,询问编号为$a$和$b$的两个数是否在同一个集合中;输入格式第一行输......
  • 并查集
    题目一共有$n$个数,编号是$1∼n$,最开始每个数各自在一个集合中。现在要进行$m$个操作,操作共有两种:Mab,将编号为$a$和$b$的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作;Qab,询问编号为$a$和$b$的两个数是否在同一个集合中;输入格式第一行输......
  • 并查集和带权并查集原理分析
    并查集是算法竞赛中常用的一种数据结构。它可以高效地处理集合之间的操作与询问。其主要功能是查询两个元素是否在同一个集合以及将两个集合合并。第一部分并查集的基本操作算法思想我们将所有元素建成很多棵树(森林),每一棵树就是一个集合。因为并查集是一个树结构,那么每......
  • 并查集笔记
    并查集导论并查集是一种数据结构,主要用于处理一些不相交集合的合并问题。一般应用在连通图、最小生成树、Kruskal算法、最近公共祖先(LCA)等算法中。举例用帮派例子理解并查集:在n个人中,分成了不同的帮派,每个帮派的人都互为朋友,朋友的朋友是朋友,例如1号和2号是朋友,1号和3号......
  • 【算法】并查集学习笔记
    1.并查集简介1.1什么是并查集并查集是一种用于管理元素所属集合的数据结构,实现为一个森林,其中每棵树表示一个集合,树中的节点表示对应集合中的元素。并查集支持两种操作:1.合并(merge):合并两个数所属的集合(合并两个树);2.查询(find):查询两个数是否在同一个集合中(查询两个数所对......
  • 并查集(Disjoint Set)
    并查集是算法竞赛中常用的一种数据结构。其主要功能是查询两个元素是否在同一个集合以及将两个集合合并。第一部分并查集的基本操作算法思想我们将所有元素建成很多树(森林),每一棵树就是一个集合,比如下图有\(\{1,2,3,4,5,6\},\{7,9,10,11,12,13\}\)两个集合。......
  • poj 2236 Wireless Network 并查集
    WirelessNetworkTimeLimit: 10000MSMemoryLimit: 65536KTotalSubmissions: 20499Accepted: 8608DescriptionAnearthquaketakesplaceinSoutheastAsia.TheACM(AsiaCooperatedMedicalteam)havesetupawirelessnetworkwiththelapcomputers,butanun......