Pagini recente » Cod sursa (job #1026216) | Cod sursa (job #1769379) | Cod sursa (job #1428382) | Cod sursa (job #3195728) | Cod sursa (job #464924)
Cod sursa(job #464924)
#include<stdio.h>
#include<stdlib.h>
#define dim 100007
using namespace std;
int *mat[dim],n,m,i,k,nod,x,y;
char viz[dim];
void dfs(int nod)
{int i;
viz[nod]=1;
for(i=1;i<=mat[nod][0];i++)
if(!viz[ mat[nod][i] ])
dfs(mat[nod][i]);
}
int main()
{
FILE *f=fopen("dfs.in","r"), *g=fopen("dfs.out","w");
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=n;i++)
{mat[i]=(int *)realloc(mat[i],sizeof(int));
mat[i][0]=0;
}
for(i=1;i<=m;i++)
{fscanf(f,"%d%d",&x,&y);
//mat[x][y]=1; mat[y][x]=1;
mat[x][0]++;
mat[x]=(int *)realloc(mat[x], (mat[x][0]+1)*sizeof(int));
mat[x][mat[x][0]]=y;
mat[y][0]++;
mat[y]=(int *)realloc(mat[y], (mat[y][0]+1)*sizeof(int));
mat[y][mat[y][0]]=x;
}
for(i=1;i<=n;i++)
if(!viz[i])
{k++;
dfs(i);
}
fprintf(g,"%d\n",k);
fclose(f);
fclose(g);
return 0;
}