Cod sursa(job #276748)

Utilizator bacerandreiBacer Andrei bacerandrei Data 11 martie 2009 12:28:16
Problema Parcurgere DFS - componente conexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<fstream.h>
#include<string.h>
ofstream fo("dfs.out");

struct lista
{
  int nod;
  lista *urm;
};
lista *g[100001];

long long n , m ; //t[100] , d[100] , f[100] , timp;
char u[100001];


void adauga(int i , int j)
{
  lista *p;
  p = new lista ; p->nod = j;
  p->urm = g[i] ; g[i] = p;
}


void citeste_graf()
{
  long i , j;
   ifstream f("dfs.in");
    f>>n>>m;
     for(i = 1 ; i <= m ; i++)
      {
	f>>i>>j;
	adauga(i , j);
	adauga(j , i);
      }
}


void df(int nod)
{
  lista *p;
   u[nod] = 1;
  // d[nod] = ++timp;
  //  cout<<nod<<" ";
     for(p = g[nod] ; p != NULL ; p = p->urm)
       if(!u[p->nod])
	{
     //	  t[p->nod] = nod;
	  df(p->nod);
	}
   // f[nod] = ++timp;
}


int main()
{
 // clrscr();
 long long nr = 0;
   citeste_graf();
    for(long i = 1 ; i <= n ; i++)
     if(u[i] == 0)
      {
	nr++;
	df(i);
      }
    fo<<nr<<"\n";
   fo.close();
 // getch();
 return 0;
}