技术标签： leecode和剑指offer刷题 算法 union find 并查集 leetcode 数据结构与算法 数据结构
关于并查集的一些基础知识以及应用，可以看我之前的一篇文章：一文搞定并查集
看完那篇文章基本可以完全掌握并查集
班上有 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。最后查看有多少个集合即可。
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文章浏览阅读461次。_electron vue项目打开慢
文章浏览阅读229次。接1、2、3、4篇。10、安装mysql支持安装fedora15或者16系统时若选择安装mysql数据库，则必须自行安装mysql开发包。因为自带默认数据库不会安装这个包。否则会遇到mysql错误：ogr_mysql.h:34:23: fatal error: my_global.h: No such file or directory#问题原因：找不到mysql头文件..._linux gdal netcdf5
文章浏览阅读1.2k次。Linux tc qdisc 模拟网络丢包延时_tc qdisc
文章浏览阅读336次。linux64bit 安装 jdk 1.7下载地址 ： https://edelivery.oracle.com/otn-pub/java/jdk/7u21-b11/jdk-7u21-linux-x64.rpm0. 卸载rpm版的jdk： #rpm -qa|grep jdk 显示：jdk-1.6.0_10-fcs 卸载：#rpm -e --nodep..._liunx64位得jdk1.7
文章浏览阅读552次。开始听到负载均衡的时候，我第一反应想到的是链路负载均衡，在此之前主要是在学习网络方面知识，像在NA、NP阶段实验做链路负载均衡时常会遇到，后来还接触到SLB负载分担技术，这都是在链路基础上实现的。 其实负载均衡可以分为硬件实现负载均衡和软件实现负载均衡。 硬件实现负载均衡：常见F5和Array负载均衡器，配套专业维护服务，但是成本昂贵。 软件实现负载均衡：常见开源免费的负载均衡软件有Ngin..._中间件应用场景nginx lvs proxy
文章浏览阅读4.7k次。多维时序 | MATLAB实现CNN-LSTM多变量时序预测目录多维时序 | MATLAB实现CNN-LSTM多变量多步预测基本介绍模型特点程序设计学习总结参考资料基本介绍本次运行测试环境MATLAB2020b，MATLAB实现CNN-LSTM多变量多步预测。模型特点深度学习使用分布式的分层特征表示方法自动提取数据中的从最低层到最高层固有的抽象特征和隐藏不变结构. 为了充分利用单个模型的优点并提高预测性能, 现已提出了许多组合模型。CNN 是多层前馈神经网络, 已被证明在提取隐藏_cnn可以进行多步预测
文章浏览阅读219次。3.1 用户配置文件和密码配置文件3.2 用户组管理3.3 用户管理3.4 usermod命令3.5 用户密码管理3.6 mkpasswd命令_polkitd:input 用户和组
文章浏览阅读670次。主成分分析，即Principal Component Analysis(PCA)，是多元统计中的重要内容，也广泛应用于机器学习和其它领域。它的主要作用是对高维数据进行降维。PCA把原先的n个特征用数目更少的k个特征取代，新特征是旧特征的线性组合，这些线性组合最大化样本方差，尽量使新的k个特征互不相关。关于PCA的更多介绍，请参考：https://en.wikipedia.org/wiki/Prin..._inprementation python code of pca
文章浏览阅读35次。发一下牢骚和主题无关：地址类型：32位的cpu，共4G间空，其中0-3G属于用户间空地址，3G-4G是内核间空地址。用户虚拟地址：用户间空程序的地址物理地址：cpu与内存之间的用使地址总线地址：外围总线和内存之间的用使地址内核逻辑地址：内存的分部或全体射映，大多数情况下，它与物理地址仅差一个偏移量。如Kmalloc分..._linux 内存条与内存地址
文章浏览阅读1.3k次，点赞2次，收藏16次。什么是自动化测试？ 做测试好几年了，真正学习和实践自动化测试一年，自我感觉这一个年中收获许多。一直想动笔写一篇文章分享自动化测试实践中的一些经验。终于决定花点时间来做这件事儿。 首先理清自动化测试的概念，广义上来讲，自动化包括一切通过工具（程序）的方式来代替或辅助手工测试的行为都可以看做自动化，包括性能测试工具（loadrunner、jmeter）,或自己所写的一段程序，用于_自动化测试中baw库指的什么
文章浏览阅读1.6w次。A0纸指的是一平方米大小的白银比例长方形纸(长为1189mm宽为841mm)。A0=1189mm*841mm A1=841mm*594mm 相当于1/2张A0纸 A2=594mm*420mm 相当于1/4.A1图纸大小尺寸：841mm*594mm 即长为841mm，宽为594mm 过去是以多少＂开＂(例如8开或16开等)来表示纸张的大小，我国采用国际标准，规定以 A0、A1、A2、.GB/T 14..._a0图纸尺寸
文章浏览阅读966次。最终效果图：UI说明：针对table本身进行增强的tree table组件。 tree的数据来源是单元格内a元素的自定义属性：level和type。具体代码如下：Java代码 DepartmentEmployeeIDposi_treetable canvas