Pagini recente » Cod sursa (job #830042) | Cod sursa (job #1045056) | Cod sursa (job #788751) | Cod sursa (job #827233) | Cod sursa (job #263344)
Cod sursa(job #263344)
#include<stdio.h>
#define xn 100001
FILE* fin=fopen("dfs.in","r");
FILE* fout=fopen("dfs.out","w");
struct lista{ int nod; lista *urm;} *g[xn];
int n,m,viz[xn],nr;
void df(int i)
{
viz[i]=nr;
lista *p;
for(p=g[i];p;p=p->urm)
if(!viz[p->nod])
df(p->nod);
}
int main()
{
int i,x,y;
lista *p;
fscanf(fin,"%d %d",&n,&m);
for(i=1;i<=m;i++)
{
fscanf(fin,"%d %d",&x,&y);
p=new lista;
p->nod=y;
p->urm=g[x];
g[x]=p;
p=new lista;
p->nod=x;
p->urm=g[y];
g[y]=p;
}
for(i=1;i<=n;i++)
if(!viz[i])
nr++,df(i);
fprintf(fout,"%d\n",nr);
fclose(fout);
return 0;
}