Pagini recente » Cod sursa (job #931238) | Cod sursa (job #2444184) | Cod sursa (job #1985534) | Clasament preONI 2006, Clasa a IX-a si gimnaziu | Cod sursa (job #163176)
Cod sursa(job #163176)
#include <stdio.h>
typedef struct nod {
int val;
nod *urm;
} *pNod;
pNod a[100001];
int comp_conexe=0,v[100001],n,m;
int citire()
{FILE *f;
int x,y;
pNod q,p;
f=fopen("dfs.in","r");
fscanf(f,"%d %d",&n,&m);
for (int i=1;i<=m;i++)
{fscanf(f,"%d %d",&x,&y);
q=new(nod);
q->val=x;
q->urm=a[y];
a[y]=q;
p=new(nod);
p->val=y;
p->urm=a[x];
a[x]=p;
}
fclose(f);
return 0;
}
int DFS(int x)
{
pNod q;
for (q=a[x];q!=NULL;q=q->urm)
if (v[q->val]==0) {v[q->val]=1;
DFS(q->val);
}
return 0;
}
int afisare()
{FILE *f;
f=fopen("dfs.out","w");
fprintf(f,"%d",comp_conexe);
fclose(f);
return 0;
}
int main()
{
citire();
for (int i=1;i<=n;i++)
if (v[i]==0) {v[i]=1;
comp_conexe++;
DFS(i);
}
afisare();
return 0;
}