Cod sursa(job #662284)

Utilizator iuyuIoana Orsa iuyu Data 16 ianuarie 2012 13:45:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<fstream> 
using namespace std; 
long x,y,n,i,m,nr; 
struct nod{int info;nod *adr;} *v[100002]; 
short viz[200002];  
void df(int nod) 
{ 
    
viz[nod]=1; 
    
while(v[nod]) 
    
{ 
       
if(!viz[v[nod]->info])       df(v[nod]->info); 
           
v[nod]=v[nod]->adr; 
    
} 
} 
 
 
int main() 
{ 
    
ifstream f("dfs.in");ofstream g("dfs.out"); 
    
f>>n>>m; 
    
for(i=1;i<=m;i++) 
    
{f>>x>>y; 
     
                
nod *p=new nod;   p->info=y;   p->adr=v[x]; v[x]=p; 
                  
nod *q=new nod;   q->info=x;   q->adr=v[y]; v[y]=q; 
    
} 
    
for(i=1;i<=n;i++) 
        
if(!viz[i]) { nr++; df(i); } 
        
g<<nr; 
    
f.close();g.close(); 
return 0;}