leetcode并查集相关经典题目(思路、分析、代码)_leetcode并查集题目-程序员宅基地

技术标签： leecode和剑指offer刷题算法 union find 并查集 leetcode 数据结构与算法数据结构

leetcode并查集相关经典题目(思路、分析、代码)

关于并查集的一些基础知识以及应用，可以看我之前的一篇文章：一文搞定并查集
看完那篇文章基本可以完全掌握并查集

文章目录

- - leetcode并查集相关经典题目(思路、分析、代码)

547. 朋友圈

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M [i] [j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例 1:
输入: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
输出: 2 
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。

分析：该题是典型的并查集应用，如果两个人是朋友，则将其归为一类，采用并查集表示，首先初始化，然后遍历，如果两个人是朋友且未在一类则unite。最后查看有多少个集合即可。

并：如果两个节点的属于一类，则并，方法是将其中一个节点的根指向另一个节点的根即可
查：判断两个节点是否是一类只需要判断他们的根是否相同
由于该题的节点数量较少，故没有过多优化。实际上可以添加一个rank数组大致表示节点所在树的高度，当合并时令低树的根指向高树的根可以降低树的高度。

class Solution {
   
    
public:
	int par[201]; 
    void init(int n) //初始化并查集
	{
   
    
		for(int i=0;i<n;i++)  //让其父结点指向自己 
			par[i]=i;	
	}
	int find(int x) //查找某节点所在树的根节点
	{
   
    
		return par[x]==x?x:par[x]=find(par[x]);  //如果自己是根节点则返回，否则向上递归,但是将par[x]指向父亲的根节点(用于优化)	
	} 
	void unite(int x,int y)
	{
   
    
		if(find(x)==find(y))//是同一类则返回 
			return;
		else
			par[find(x)]=find(y); //让其中一个节点的根指向另一个节点的根即可 
	}
	int findCircleNum(vector<vector<int>>& M) 
	{
   
    
		int row=M.size();
		if(row==0) return 0;
		init(row); //初始化row个节点
		for(int i=0;i<row-1;i++)
		for(int j

本文链接：https://blog.csdn.net/dingdingdodo/article/details/106272854

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

react学习总结6--构建工具Gulp、Browserify（二）_react gulp-程序员宅基地

文章浏览阅读1k次。react 学习总结–构建工具Gulp、Browserify（二）1.html 文件处理gulp-htmlmin 插件用于压缩html，可以进行配置，下边是配置信息（选填） var gulp = require('gulp'), htmlmin = require('gulp-htmlmin'); gulp.task('htmlmin', function ()_react gulp

开关电源输入：共模电感，X电容，Y电容，差摸电感理论计算！_共模电感和y电容在滤波方面的区别-程序员宅基地

文章浏览阅读7.6k次，点赞3次，收藏69次。转自：https://mp.weixin.qq.com/s/qp_DSBGKdjNo2-lO2s5v7Q引言在开关电源中，EMI滤波器对共模和差模传导噪声的抑制起着显著的作用。在研究滤波器原理的基础上，探讨了一种对共模、差模信号进行独立分析，分别建模的方法，最后基于此提出了一种EMI滤波器的设计程序。高频开关电源由于其在体积、重量、功率密度、效率等方面的诸多优点，已经被广泛地应用于工业..._共模电感和y电容在滤波方面的区别

IntelliJ IDEA 设置注释模板（Mac）_mac idea 设置注解格式-程序员宅基地

文章浏览阅读7.9k次。类注释模板设置：点击 preferences ，搜索 File and Code Template ,在 Files tab 页下，选择 Class，在类名上面添加模板：/** * @program ${PROJECT_NAME} * @description: ${TODO} * @author: ${USER} * @create: ${YEAR}/${MONTH}/${DAY}..._mac idea 设置注解格式

sizeof用法 _sizeof(4.0+2)-程序员宅基地

文章浏览阅读2k次。Sizeof用法本文主要包括二个部分，第一部分重点介绍在VC中，怎么样采用sizeof来求结构的大小，以及容易出现的问题，并给出解决问题的方法，第二部分总结出VC中sizeof的主要用法。1、 sizeof应用在结构上的情况请看下面的结构：struct MyStruct{double dda1;char dda;int type};对结构MyStruct采用_sizeof(4.0+2)

阅读小结：Large-Margin Softmax Loss for Convolutional Neural Networks_large-margin softmax loss的代码-程序员宅基地

文章浏览阅读2.2k次，点赞3次，收藏4次。徐博最近一直在看我博客，肯定是想看我什么时候不更新，然后好嘲笑我。当然，不排除徐博已经爱上我的可能。What：改进SoftmaxLoss，显式的控制类内的距离，（不让已经对的样本score太高，影响训练）可以防止过拟合。回顾SoftmaxLoss：1. Softmax 就是一个把一个向量归一的函数，输出也是向量。在matlab里就3行代码：% X_large-margin softmax loss的代码

后端java解析复杂嵌套json_java 解析复杂类型的json-程序员宅基地

文章浏览阅读6.2k次。其实不是很复杂百度翻译传过来的json数据：{"from":"zh","to":"en","trans_result":[{"src":"高度600米","dst":"Height 600 meters"}]}现在要取出dst对应的值：Height 600 meters String date="{"from":"zh","to":"en","trans_result":[_java 解析复杂类型的json