Pagini recente » Cod sursa (job #2740682) | Cod sursa (job #3268650) | Cod sursa (job #1426377) | Cod sursa (job #2794812) | Cod sursa (job #2260088)
#include <fstream>
#include <vector>
#include <functional>
#include <iostream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int main()
{
int n,m;
fin>>n>>m;
int ans=n;
vector<int>h(n),t(n);
for(int i=0;i<n;i++)
{
t[i]=i;
h[i]=1;
}
function<int(int)>dad=[&](int a)
{
if(a==t[a]) return a;
t[a]=dad(t[a]);
return t[a];
};
function<void(int,int)>unite=[&](int a,int b)
{
a=dad(a);
b=dad(b);
if(a==b)
return;
ans--;
if(h[a]<h[b])
{
t[a]=b;
}
else
{
t[b]=a;
if(h[a]==h[b])
h[a]++;
}
};
while(m--)
{
int a,b;
fin>>a>>b;
a--;
b--;
unite(a,b);
}
fout<<ans<<"\n";
return 0;
}