Pagini recente » Cod sursa (job #1116524) | Cod sursa (job #362334) | Cod sursa (job #1697049) | Cod sursa (job #1684073) | Cod sursa (job #1044246)
#include <stdio.h>
#define N 100000
typedef struct{
int nr,urm;
}lista;
FILE *in,*out;
lista v[2*N+1];
int ultim[N+1],vizitat[N+1];
void dfs(int n){
int i;
vizitat[n]=1;
i=ultim[n];
while(i>0){
if(!vizitat[v[i].nr]){
dfs(v[i].nr);
}
i=v[i].urm;
}
return ;
}
int main(){
in=fopen("dfs.in","r");
out=fopen("dfs.out","w");
int i,nrc,n,m,x,y;
fscanf(in,"%d%d",&n,&m);
for(i=1;i<=m;i++){
fscanf(in,"%d%d",&x,&y);
v[2*i-1].nr=x;
v[2*i-1].urm=ultim[y];
ultim[y]=2*i-1;
v[2*i].nr=y;
v[2*i].urm=ultim[x];
ultim[x]=2*i;
}
nrc=0;
for(i=1;i<=n;i++){
if(!vizitat[i]){
dfs(i);
nrc++;
}
}
fprintf(out,"%d",nrc);
return 0;
}