Cod sursa(job #359551)

Utilizator TiberiurRus Tiberiu Gabriel Tiberiur Data 27 octombrie 2009 14:17:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream.h> 
#include <iostream.h> 
#include <stdio.h> 
using namespace std; 
long i,comp_conex=0; 
long n,m,vizitat[100005]; 
typedef struct nod 
{     
int info; 
    
nod *urm; 
} *TNod; 
TNod v[100005]; 
 
void citire() 
{int i,j,k,x,y; 

ifstream f("dfs.in"); 
 
    f>>n>>m; 
    TNod p; 
 
          for (i = 1; i <= m; i++)     
{     f>>x>>y; 
        
          p=new nod;         
p->info=x; 
        
p->urm=v[y]; 
        
v[y]=p; 
        
p=new nod; 
       
p->info=y; 
        
p->urm=v[x]; 
        
v[x]=p; 
    
} 
    
f.close(); 
} 
 
void df(int nod) 
{TNod p; 
    
vizitat[nod] = 1;     
for (p=v[nod];p!=NULL;p=p->urm) if(!vizitat[p->info]) df(p->info); 
} 
void afisare() 
{ofstream g("dfs.out"); 
g<<comp_conex; 
g.close(); 
}  
 
int main() 
{int j,k,indice=1; 
 
citire(); 
  
 
while(indice!=0) 
{indice=0; for(k=1;k<=n;k++) 

if(vizitat[k]==0) 
  
{indice=1;comp_conex++;df(k);} 
} 
afisare(); 
return 0; 
}