Pagini recente » Cod sursa (job #912707) | Cod sursa (job #803360)
Cod sursa(job #803360)
#include<stdio.h>
#include<stdlib.h>
#define N 200000
#define M 100001
FILE *in;
FILE *out;
struct muchie{
int x,y;
};
int n,m;
struct muchie vm[N];
int *a[M];
int c[M];
int g[M];
int viz[M];
void citire()
{
int i;
fscanf(in,"%d%d",&n,&m);
for(i=0;i<m;i++)
{
fscanf(in,"%d%d",&vm[i].x,&vm[i].y);
g[vm[i].x]++;
g[vm[i].y]++;
}
for(i=1; i<=n; i++)
a[i] = (int*) malloc(g[i]*sizeof(int));
for(i=0; i<m; i++)
{
a[vm[i].x][++c[vm[i].x]]=vm[i].y;
a[vm[i].y][++c[vm[i].y]]=vm[i].x;
}
}
void dfs(int x)
{
viz[x]=1;
int i,y;
for(i=1;i<=g[x];i++)
{
y=a[x][i];
if(!viz[y])
dfs(y);
}
}
int main()
{
in = fopen("dfs.in","r");
out = fopen("dfs.out","w");
int i,count=0;
citire();
for(i=1;i<=n;i++)
{
if(!viz[i])
{
count++;
dfs(i);
}
}
fprintf(out,"%d\n",count);
return 0;
}