Cod sursa(job #650281)

Utilizator I.AlexandruIlie Alexandru I.Alexandru Data 17 decembrie 2011 18:55:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<fstream>
#define max 100001
using namespace std;

typedef struct nod{
int info;
nod *next;
}pnod;

pnod *lv[max];
int viz[max];
int n, m, i, x, y, k;
ifstream f("dfs.in");
ofstream g("dfs.out");

void adauga(int x, int y)
{pnod *aux=new nod;
aux->info=y;
aux->next=lv[x];
lv[x]=aux;
}

void df(int nod)
{viz[nod]=1;
pnod *aux=lv[nod];
while(aux!=NULL)
     {if(!viz[aux->info])
         df(aux->info);
      aux=aux->next;
     }
}

int main()
{f>>n;
f>>m;

for(i=m; i>0; i--)
   {f>>x;
    f>>y;
    adauga(x, y);
    adauga(y, x);
   }

for(i=1; i<=n; i++)
   if(!viz[i])
     {k++;
      df(i);
     }
     
g<<k;
return 0;
}