目录
思路
建立一个数组存储父节点,初始化counts为总数,有连接的节点将朋友圈的个数减1。
#include<iostream>
#include<vector>
using namespace std;
int finds(vector<int>& parents,int q){
int x=q;
while(parents[x]!=x){
x=parents[x];
}
return x;
}
int main()
{
int n=4;
int counts=n;
vector<vector<int>> friends{{1,3},{2,4}};
vector<int> parents(n+1,0);
for(int i=1;i<=n;i++)
parents[i]=i;
for(int i=0;i<friends.size();i++)
{
int q=friends[i][0];
int p=friends[i][1];
int rootq=finds(parents,q);
int rootp=finds(parents,p);
if(rootp==rootq)
continue;
parents[q]=rootp;
counts--;
}
cout<<counts;
}
优化1:平衡优化,将小树放在大树后面
void union(vector<int> &parents,vector<int> &size,int q,int p){
int rootq=finds(parents,q);//找到q的根节点
int rootp=finds(parents,p);//找到p的根节点
if(rootp==rootq) return ;
if(size[rootq]>size[rootp]){
parents[rootp]=rootq;
size[rootq]+=size[rootp];
}
else {
parents[rootq]=rootq;
size[rootp]+=size[rootq];
}
}
优化2:每次查找的父节点的时候压缩路径
int find(vector<int> parents,int q){
int x=q;
while(parents[x]!=x){
parents[x]=parents[parents[x]];//将父节点指向其父节点的父节点,压缩了路径
x=parents[x];
return x;
}