Pagini recente » Borderou de evaluare (job #1755360) | Cod sursa (job #2643581) | Borderou de evaluare (job #231760) | Cod sursa (job #3233910) | Cod sursa (job #3169522)
#include <fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
int n,m;
int tata[100001];
int h[100001];
int ffind(int x)
{
while(tata[x]!=0)
x=tata[x];
return x;
}
void uunion(int r1,int r2)
{
if(h[r1]<h[r2])
tata[r1]=r2;
else if(h[r1]>h[r2])
tata[r2]=r1;
else
{ tata[r1]=r2;
h[r2]++;}
}
int main() {
int i,x,y;
in>>n>>m;
for(i=1;i<=m;i++)
{
in>>x>>y; // muchie
// lipesc comp conexa a lui + comp conexa a lui y
int r1=ffind(x);
int r2=ffind(y);
if(r1!=r2)
uunion(r1,r2);
}
int cnt=0;
for(i=1; i<=n; i++)
if(tata[i]==0) cnt++;
out<<cnt;
return 0;
}