Cod sursa(job #263344)

Utilizator igsifvevc avb igsi Data 20 februarie 2009 11:27:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#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;
}