Pagini recente » Cod sursa (job #1669674) | Cod sursa (job #1923156) | Cod sursa (job #3278772) | Cod sursa (job #2698193) | Cod sursa (job #577962)
Cod sursa(job #577962)
#include <fstream>
#include <cstdio>
#define NMAX 100007
#define Input "dfs.in"
#define Output "dfs.out"
using namespace std;
int tata[NMAX],h[NMAX],N,M,nrc=0;
inline void uneste(int a,int b)
{
if(h[a] > h[b])
tata[b]=a;
else
tata[a]=b, h[b]+=(h[a]==h[b])?1:0;
}
inline int cauta(int a)
{
int r=a,y=a,t;
while(tata[r]) r=tata[r];
while(y!=r)
{
t=tata[y];
tata[y]=r;
y=t;
}
return r;
}
int main(){
ifstream fin(Input);
freopen (Output,"w",stdout);
int i,e1,e2,v1,v2;
fin>>N>>M;
for(i=1; i<=M; i++)
{
fin>>e1>>e2;
v1=cauta(e1);
v2=cauta(e2);
if(v1 != v2)
uneste(v1,v2);
}
for(i=1; i<=N; i++)
if(tata[i] == 0)
nrc++;
printf("%d\n",nrc);
return 0;
}