Cod sursa(job #356088)

Utilizator curcubeuPop Simina curcubeu Data 13 octombrie 2009 14:31:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 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; 
} *pNod; 
pNod v[100005]; 
 
void citire() 
{int i,j,k,x,y; 

ifstream f("dfs.in"); 
 
f>>n>>m; 
 
pNod nou; 
 
for (i = 1; i <= m; i++)     
{ 
     
f>>x>>y; 
        
nou=new nod;         
nou->info=x; 
        
nou->urm=v[y]; 
        
v[y]=nou; 
        
nou=new nod; 
       
nou->info=y; 
        
nou->urm=v[x]; 
        
v[x]=nou; 
    
} 
    
f.close(); 
} 
 
void df(int nod) 
{pNod nou; 
    
vizitat[nod] = 1;     
for (nou=v[nod];nou!=NULL;nou=nou->urm) if(!vizitat[nou->info]) df(nou->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; 
}