Cod sursa(job #789963)

Utilizator preg_concursPregatire Concurs preg_concurs Data 19 septembrie 2012 22:36:00
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include<fstream>


using namespace std;

typedef struct no{

  int val;
  no *urm;
} nod;

 nod *vecini[100001];

int viz[100001];

void dfs(int k){


   nod *aux=vecini[k];
   viz[k]=1;

   while(aux){
      dfs(aux->val);
      aux=aux->urm;
   }

}


int main()
{
    int n,m,cont,i,x,y;
    ifstream f("dfs.in");
    ofstream g("dfs.out");

    f>>n>>m;

  for(i=1;i<=m;i++)
   {
     f>>x>>y;


   nod *aux=new nod;
   aux->val=y;
   aux->urm=vecini[x];
   vecini[x]=aux;
   }

   cont=0;
   for(i=1;i<=n;i++)
    if(!viz[i])
    {
        cont++;
        dfs(i);
    }

     g<<cont;
    return 0;
}