Cod sursa(job #482807)

Utilizator Smaug-Andrei C. Smaug- Data 5 septembrie 2010 12:06:56
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 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);
    v[aux]++;
  }
  
  Si=1; Stack[Si]=1; d[1]=1; count = 1;

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

  printf("%d\n", count);

  return 0;

}