Cod sursa(job #661697)

Utilizator sorina.vasileVasile Sorina sorina.vasile Data 14 ianuarie 2012 22:15:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<fstream>
using namespace std;
int viz[100002];

typedef struct nod { int info;
                     nod *vec;};
nod *v[100002];

void adauga_vecin(int i, int j)
{ nod *c;     
 c=new nod;
 c->info=j;
 c->vec=v[i];
 v[i]=c; }

void DF(int x)
{ nod *c;
  c=v[x];
  viz[x]=1;
  while(c!=NULL)
{ if(viz[c->info]==0)
  DF(c->info);
  c=c->vec;}
}
  

int main()
{    int N,M, a, b, comp_con;  
     fstream f("dfs.in", ios::in);
     fstream g("dfs.out",ios::out);  
    f>>N;
    f>>M;
    
for(int i=1;i<=M;i++)
{f>>a>>b;
 adauga_vecin(a,b);
 adauga_vecin(b,a); }
 
 for(int i=1;i<=N;i++)
 if(viz[i]==0)
 {DF(i); comp_con++;}
 
 g<<comp_con;
 
 f.close();
 g.close();
 return 0;
}