当前位置:网站首页>leetcode 547.省份数量 并查集
leetcode 547.省份数量 并查集
2022-08-10 19:06:00 【Alkali!】
题目描述
思路
直接利用并查集的思想即可。
并查集
代码
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
vector<int> p(210);
for(int i=0;i<isConnected.size();i++)
p[i]=i; //初始化并查集的数组,每个元素的根节点都为自身,也即没有父结点、根节点,都是独立的
for(int i=0;i<isConnected.size();i++)
for(int j=0;j<isConnected[0].size();j++)
{
if(isConnected[i][j]==1)
{
int a=find(i,p);
int b=find(j,p);
if(a!=b) //如果不是一个集合
p[b]=a; //路径压缩合并
}
}
//怎么计算一共有多少个集合?
int res=0;
for(int i=0;i<isConnected.size();i++)
if(p[i]==i) res++; //只要数一共有多少节点被作为根节点即可,根节点与集合个数一一对应
return res;
}
//路径压缩去查找的同时压缩路径
int find(int x,vector<int>& p)
{
if(x!=p[x]) p[x]=find(p[x],p);
return p[x];
}
};
边栏推荐
猜你喜欢
QoS服务质量七交换机拥塞管理
QoS Quality of Service Eight Congestion Avoidance
巧用RoaringBitMap处理海量数据内存diff问题
[教你做小游戏] 只用几行原生JS,写一个函数,播放音效、播放BGM、切换BGM
【Knowledge Sharing】What is SEI in the field of audio and video development?
测试/开发程序员值这么多钱么?“我“不会愿赌服输......
3D游戏建模学习路线
Optimizing Bloom Filter: Challenges, Solutions, and Comparisons论文总结
Optimization is a habit The starting point is to 'stand close to the critical'
[Natural Language Processing] [Vector Representation] PairSupCon: Pairwise Supervised Contrastive Learning for Sentence Representation
随机推荐
电脑为什么会蓝屏的原因
网络虚拟化
云渲染的应用正在扩大,越来越多的行业需要可视化服务
TDD、FDD是什么意思?
含有PEG 间隔基和一个末端伯胺基团(CAS:1006592-62-6)化学试剂
测试/开发程序员值这么多钱么?“我“不会愿赌服输......
Redis 持久化机制
你不知道的浏览器页面渲染机制
argparse——命令行参数解析
QoS Quality of Service Seven Switch Congestion Management
Pt/CeO2单原子纳米酶|[email protected] NPs纳米酶|碳纳米管负载铂颗粒纳米酶|白血病拮抗多肽修饰的FeOPtPEG复合纳米酶
西安Biotin-PEG8-IA_IA-PEG8-生物素供应商
803. 区间合并(贪心)左端点、右端点排序均可
回老家去?
Rider调试ASP.NET Core时报thread not gc-safe的解决方法
QoS服务质量八拥塞避免
第四届“传智杯”全国大学生IT技能大赛(初赛A组) 补题
子域名收集&Google搜索引擎语法
铱钌合金/氧化铱仿生纳米酶|钯纳米酶|GMP-Pd纳米酶|金钯复合纳米酶|三元金属Pd-M-Ir纳米酶|中空金铂合金纳米笼核-多空二氧化硅壳纳米酶
基于TCP的聊天系统