Cod sursa(job #548459)

Utilizator anaa_mariaaana dima anaa_mariaa Data 7 martie 2011 14:31:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include<fstream.h>
#define NM 100001
ifstream in("dfs.in");
ofstream out("dfs.out");

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

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

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

void build(){
int i,x,y;
in>>n>>m;
for(i=1;i<=m;i++){
  in>>x>>y;
  add(l[x],y);
  add(l[y],x);}
  }

void df(int x){
int y;
nod*nc=urm[x];
  while(nc){
  viz[x]=cc;
  y=nc->nr;
  nc=nc->next;
    if(!viz[y])
    df(y);
    urm[x]=nc;}
    }

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);}
out<<cc;
return 0;}