Cod sursa(job #361366)

Utilizator swxxIoo Andrei Rares swxx Data 4 noiembrie 2009 20:03:35
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb

#include<fstream>
#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 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; 
}