#include<bits/stdc++.h>
using namespace std;
// 并查集
int s[100001];
bool st[100001];
int needPath=0;
void init(int n){
for(int i=1;i<=n;i++){
s[i]=-1;
st[i]=false;
}
}
int Find(int a){
int x=a;
while(s[x]>0){
x=s[x];
}
return x;
}
void Union(int root1,int root2){
root1=Find(root1);
root2=Find(root2);
if(root2==root1)return ;
else{
s[root2]=root1;
}
}
int main(){
int n,m;
cin>>n>>m;
init(n);
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
Union(a,b);
}
for(int i=1;i<=n;i++){
int root=Find(i);
// cout<<root<<endl;
// if(!st[root]){
// st[root]=true;
// needPath++;
// }
if(s[i]==-1)needPath++;
}
cout<<needPath-1;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla