Cod sursa(job #149527)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 5 martie 2008 20:24:40
Problema Parcurgere DFS - componente conexe Scor 85
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <string>
#define NMAX 100000+10
#define MMAX NMAX*(NMAX+1)/2

using namespace std;

long n, m, vec[MMAX], poz[NMAX], comp[NMAX], nr;   

void df(long x)
{
  long i;

  comp[x] = nr;
  for ( i = poz[x]+1; i <= poz[x+1]; ++i)
    if (!comp[vec[i]])
      df(vec[i]);

}

int main(void)
{
  long i, *a, *b, k;

  freopen("dfs.in", "r", stdin);
  freopen("dfs.out", "w", stdout);

  scanf("%ld %ld", &n, &m);
  a = (long *) malloc ( m * sizeof(long) );
  b = (long *) malloc ( m * sizeof(long) );
  for (i = 1; i <= m; ++i)
    {
     scanf("%ld %ld", a+i, b+i);
     poz[a[i]]++;
     poz[b[i]]++;
    }
  for (i = 1; i <= n; ++i)
     poz[i] += poz[i-1];
  for (i = 1; i <= m; ++i)
    {
     vec[ poz[a[i]] ] = b[i];
     vec[ poz[b[i]] ] = a[i];
     poz[a[i]]--;
     poz[b[i]]--;
    }
  free(a), free(b);
  nr = 0, k = 1;
  while (k <= n)
   {
    if (!comp[k])
	  nr++, df(k);
    k++;
   }
  printf("%ld", nr);

  return 0;
}