Cod sursa(job #359798)

Utilizator alex@ndraAlexandra alex@ndra Data 28 octombrie 2009 13:16:59
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<fstream>
using namespace std;

typedef struct nod
{
   int info;
   nod*urm;
} *TNOD;

TNOD v[100000];
int n, m, i, j,nrc=0,vizitat[100000];

void citire()
{
     int x, y;
     TNOD p;
     
     ifstream f("dfs.in");
        f>>n>>m;
        
        for(i=1;i<=m;i++)
           {
              f>>x>>y;
              
              p=new nod;
              p->info=x;
              p->urm=v[y];
              v[y]=p;
              
              p=new nod;
              p->info=y;
              p->urm=v[x];
              v[x]=p;
           }
     f.close();
     
}

void dfs(int nod)
{
     TNOD p;
     
     vizitat[nod]=1;
     
     for(p=v[nod];p!=NULL;p=p->urm)
          if(!vizitat[p->info])
             dfs(p->info);
             
}

void afisare()
{
     ofstream g("dfs.out");
        g<<nrc;
     g.close();
}

int main()
{  int k;
    citire();
    
    for(k=1;k<=n;k++)
       if(vizitat[k]==0)
          {
            nrc++;
            dfs(k);
          }
    
    afisare();



return 0;

}