Cod sursa(job #283445)

Utilizator MeteoraMoarteaDinCarpati Meteora Data 19 martie 2009 10:05:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<fstream.h>   
struct nod{ int inf;   
          nod *leg;}*l[100005];   
int s[100005];   
unsigned long m,n;   
void df(int nod1)   
{    
  s[nod1]=1;   
 while(l[nod1])      
 {      
    if(s[l[nod1]->inf]==0)      
      df(l[nod1]->inf);      
   l[nod1]=l[nod1]->leg;      
 }     
 }   
int main()   
{   
 unsigned long nr=1,i,j,k;   
 ifstream f("dfs.in");   
 f>>n>>m;   
 for(k=1;k<=m;k++)   
 {   
  f>>i>>j;   
  nod *p;   
  p=new nod;   
  p->inf=i;   
  p->leg=l[j];   
  l[j]=p;   
  p=new nod;   
  p->inf=j;   
  p->leg=l[i];   
  l[i]=p;   
  }   
 df(1);   
 for(i=1;i<=n;i++)   
{      
 if(s[i]==0){nr++;      
         df(i);      
        }      
 }      
 ofstream g("dfs.out");   
 g<<nr;   
 return 0;   
}