Cod sursa(job #167673)

Utilizator portocalaDiculescu Elena Alexandra portocala Data 29 martie 2008 21:52:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
//componente conexe
#include<fstream.h>
#define dim 100001
long n,m,max;
int w[dim];
struct nod
{long info;
nod *urm;
} *v[dim],*p,*ult[dim];

void adauga(long x,long y)
{//lista lui x,daca nu exista o creem
 if(v[x]==0)
 {v[x]=new nod;
  v[x]->info=y;
  v[x]->urm=0;
  ult[x]=v[x];
  }
 else  //altfel ii adaugam pe y
  {p=new nod;
   p->info=y;
   p->urm=0;
   ult[x]->urm=p;
   ult[x]=ult[x]->urm;
  }
//lista lui y,la fel ca la x
 if(v[y]==0)
 {v[y]=new nod;
  v[y]->info=x;
  v[y]->urm=0;
  ult[y]=v[y];
  }
 else
  {p=new nod;
   p->info=x;
   p->urm=0;
   ult[y]->urm=p;
   ult[y]=ult[y]->urm;
  }
}

void dfs(long i)
{w[i]=1;
  if(v[i])
   {if(!w[v[i]->info])
     dfs(v[i]->info);
    while(v[i]->urm)
     {v[i]=v[i]->urm;
      if(!w[v[i]->info])
       dfs(v[i]->info);
     }
   }
}

int main()
{ifstream f("dfs.in");
f>>n>>m;
long i,x,y;
for(i=1;i<=m;i++)
 {f>>x>>y;
  adauga(x,y);
 }
for(i=1;i<=n;i++)
 if(!w[i]){max++;dfs(i);}
ofstream g("dfs.out");
g<<max<<'\n';
g.close();
return 0;
}