Skip to content

Instantly share code, notes, and snippets.

@ik11235
Created January 3, 2015 14:53
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ik11235/26ff42eaa843a22ff330 to your computer and use it in GitHub Desktop.
Save ik11235/26ff42eaa843a22ff330 to your computer and use it in GitHub Desktop.
#include<iostream>
#include<set>
using namespace std;
int par[100002];
int find(int x)
{
if(par[x]==x)
return x;
else
return par[x]=find(par[x]);
}
void ufunion(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)return;
par[y]=x;
}
int main()
{
int n,m;
cin>>n>>m;
int cnt=0;
for(int i=0;i<n;i++)par[i]=i;
for (int i=0; i<m; i++) {
int a,b;
cin>>a>>b;
a--,b--;
ufunion(a,b);
}
set<int> hash;
for (int i=0; i<n;i++)
hash.insert(find(i));
cout<<hash.size()-1<<endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment