Cod sursa(job #482810)

Utilizator Smaug-Andrei C. Smaug- Data 5 septembrie 2010 12:44:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstdio>
#include <vector>
#include <string>
using namespace std;

#define MAXN 100010

int main(){

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

  vector <int> G[MAXN];
  int d[MAXN], Stack[MAXN], v[MAXN], i, Si, aux, N, M, j, count;

  memset(v, 0, sizeof(v));
  memset(d, 0, sizeof(d));
  
  scanf("%d%d", &N, &M);
  for(i = 1; i <= M; i++){
    scanf("%d%d", &aux, &j);
    G[aux].push_back(j);
    G[j].push_back(aux);
    v[aux]++;
    v[j]++;
  }

  count = 0;

  for(aux = 1; aux <= N; aux++){
    if(!d[aux]){
      count++; Si=1; Stack[Si]=aux; d[aux]=1; 
      
      while(Si > 0){
	i = Stack[Si];
	Si--;
	for(j = 0; j < v[i]; j++){
	  //printf("S:%d; V:%d; N:%d; J:%d\n", aux, v[i], G[i][j], j);
	  if(!d[G[i][j]]){
	    Stack[++Si]=G[i][j];
	    d[Stack[Si]]=1;
	  }
	}
      }
    }
  }
  
  printf("%d\n", count);

  return 0;

}