Cod sursa(job #548474)

Utilizator petrescu.andreeapetrescu andreea petrescu.andreea Data 7 martie 2011 14:41:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream.h>
#define NM 100001
ifstream fin("dfs.in");
ofstream fout("dfs.out");


struct nod{
 int nr;
 nod *next;
 };

int m,n,viz[NM],cc;
nod *l[NM], *urm[NM];

void add(nod *&l ,int x){
 nod*m=new(nod);
 m->nr=x;
 m->next=l;
 l=m;
 }

void build(){
int x,y,i;
fin>>n>>m;
for(i=0;i<m;i++){
   fin>>x>>y;
 add(l[x],y);
 add(l[y],x);
 }
   }
void df(int x){
int y;
nod*uc=urm[x];
  while(uc){
   viz[x]=cc;
   y=uc->nr;
   uc=uc->next;
  if(!viz[y])
    df(y);
    urm[x]=uc;
    }
     }

int main(){
int i;
build();
for(i=1;i<=n;i++)
  urm[i]=l[i];
for(i=1;i<=n;i++)
  if(!viz[i])
  { cc++;
    df(i);
    }
fout<<cc;
return 0;
}