Pagini recente » Cod sursa (job #3239771) | Cod sursa (job #3244691) | Cod sursa (job #1711542) | Cod sursa (job #1962911) | Cod sursa (job #1522380)
#include <stdio.h>
#include <stdlib.h>
typedef struct nod
{
int v;
struct nod *urm;
}NOD;
NOD *graf[100001];
char* marc;
int n,m,nrComp;
void add(int index,int varf)
{
NOD *p=(NOD*)malloc(sizeof(NOD));
p->v=varf;
p->urm=graf[index];
graf[index]=p;
}
void citire()
{
int i,a,b;
FILE *f=fopen("dfs.in","r");
fscanf(f,"%d%d",&n,&m);
marc=(char*)malloc((n+1)*sizeof(char));
for(i=1; i<=n; i++)
graf[i]=NULL, marc[i]=0;
for(i=0; i<m; i++)
{
fscanf(f,"%d%d",&a,&b);
add(a,b);
add(b,a);
}
fclose(f);
}
void dfs(int v)
{
NOD *p;
for(p=graf[v]; p!=NULL; p=p->urm)
if(marc[p->v]==0)
{
marc[p->v]=1;
dfs(p->v);
}
}
void rezolvare()
{
int i,ok;
for(i=1; i<=n; i++)
if(marc[i]==0)
{
marc[i]=1;
nrComp++;
dfs(i);
}
}
void afisare()
{
FILE *g=fopen("dfs.out","w");
fprintf(g,"%d\n",nrComp);
fclose(g);
}
int main()
{
citire();
rezolvare();
afisare();
return 0;
}