Cod sursa(job #153045)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 10 martie 2008 03:16:46
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <string>
#define NMAX 100000+10
#define MMAX 200000+10

using namespace std;

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

inline void cit(unsigned &x){
	x=0;
	while (lin[poz]<'0' || lin[poz]>'9'){
          poz++;
	      if (poz == Dim) fread(lin, 1, Dim, stdin), poz=0;   
    }
	while (lin[poz]>='0' && lin[poz]<='9'){
		x = 10*x+lin[poz++]-'0';     
        if (poz == Dim) fread(lin, 1, Dim, stdin), poz=0; 
	}            
}


inline 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);

  cit(n); cit(m);
  a = (long *) malloc ( m * sizeof(long) );
  b = (long *) malloc ( m * sizeof(long) );
  for (i = 1; i <= m; ++i)
    {
	 cit(a[i]); cit(b[i]);
     poz[a[i]]++;
     poz[b[i]]++;
    }
  for (i = 1; i <= n+1; ++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 = 0;
  while (k < n)
   {
    k++;
    if (!comp[k])
	  nr++, df(k);
   }
  printf("%ld", nr);

  return 0;
}