Pagini recente » Cod sursa (job #318027) | Cod sursa (job #573902) | Cod sursa (job #1287905) | Cod sursa (job #2636159) | Cod sursa (job #1075662)
#include<stdio.h>
#include<stdlib.h>
#define Nmax 100001
FILE *in,*out;
int n,m,x,y;
int nrc;
int viz[Nmax];
int * A[Nmax];
void dfs(int k);
int main(void)
{
in=fopen("dfs.in","rt");
out=fopen("dfs.out","wt");
fscanf(in,"%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
A[i]=(int *)realloc(A[i],sizeof(int));
A[i][0]=0;
}
for(int i=1;i<=m;i++)
{
fscanf(in,"%d%d",&x,&y);
A[x][0]++;
A[x]=(int *)realloc(A[x],(A[x][0]+1)*sizeof(int));
A[x][A[x][0]]=y;
A[y][0]++;
A[y]=(int *)realloc(A[y],(A[y][0]+1)*sizeof(int));
A[y][A[y][0]]=x;
}
for(int i=1;i<=n;i++)
{
if(!viz[i])
{
nrc++;
viz[i]=nrc;
dfs(i);
}
}
fprintf(out,"%d",nrc);
fclose(in);
fclose(out);
return 0;
}
void dfs(int k)
{
for(int i=1;i<=A[k][0];i++)
{
if(!viz[A[k][i]])
{
viz[A[k][i]]=nrc;
dfs(A[k][i]);
}
}
}