Cod sursa(job #158155)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 13 martie 2008 14:36:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
//Componente conexe
#include <cstdio>
typedef struct nod{int info;
                   nod *urm;}NOD;
NOD *prim[100002],*ult[100002];
int n,m,viz[100002],nr=0;
void add(int where,int what){
     NOD *p;
     p=new NOD;
     p->info=what;
     p->urm=NULL;
     if (prim[where]==NULL) prim[where]=ult[where]=p;
                       else {ult[where]->urm=p;
                             ult[where]=p;}
     }   
void citeste(){
     int i,j,k;
     freopen("dfs.in","r",stdin);
     scanf("%d %d",&n,&m);
     for (i=1;i<=n;i++) {prim[i]=NULL;
                         viz[i]=0;}
     for (k=1;k<=m;k++) {scanf("%d %d",&i,&j);
                         add(i,j);
                         add(j,i);}
     }
void df(int vf){
     NOD *p;
      viz[vf]=1;
      p=prim[vf];
      while (p!=NULL) {if (viz[p->info]==0) df(p->info);
                       p=p->urm;}
      }
void solve(){
     int i;
     for (i=1;i<=n;i++) if (!viz[i]) {nr++;
                                      df(i);}
     freopen("dfs.out","w",stdout);
     printf("%d",nr);
     fclose(stdout);
     }
int main(){
    citeste();
    solve();
    return 0;
}