Cod sursa(job #361336)

Utilizator butabuta radu gabriel buta Data 4 noiembrie 2009 17:33:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream.h>
using namespace std; 


long n,m,vizitat[100005],nrc;
 
typedef struct nod 
{     
 int info; 
    
 nod *urm; 
} *TNod; 

TNod v[100005]; 
 
void citire() 
{
     int i,j,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<<nrc; 
  g.close(); 
}  
 
int main() 
{int j,ok=1,k; 
 
citire(); 
  
 for(k=1;k<=n;k++) 
     if(vizitat[k]==0) 
       {
        nrc++;
        df(k);
       } 
 
afisare(); 
return 0; 
}