Cod sursa(job #359795)

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

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

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

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()
{
    citire();
    
    for(j=1;j<=n;j++)
       if(vizitat[j]==0)
          {
            nrc++;
            dfs(j);
          }
    
    afisare();



return 0;

}