Cod sursa(job #695858)

Utilizator biroBiro Alexandru biro Data 28 februarie 2012 15:12:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <algorithm>
#include <stdio.h>

using namespace std ;

struct nod{
  int info ;
  nod *urm ;
} ;

nod *v[100001] ;
int viz[100001] ;

void adauga(int ur , int inf) {
  nod *p=new nod;
  p->info = inf ;
  p->urm=v[ur] ;
  v[ur]=p ;
}

void df(int poz) {
  viz[poz]=1;
  nod *q=v[poz] ;
  while(q!=NULL) {
    if(viz[q->info]==0) {
      viz[q->info]=10;
      df(q->info);
    }
    q=q->urm;
  }
}

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

  int n , m ;
  scanf ("%d%d" , &n , &m) ;
  int x , y ;
  for (int i=1 ; i<=m ; ++i) {
    scanf("%d%d",&x,&y);
    adauga(x,y);
    adauga(y,x);
  }
  int rez=0 ;
  for(int i=1;i<=n;++i) {
    if (viz[i]==0) {
      ++rez ;
      df(i) ;
    }
  }
  
  printf ("%d" , rez) ;

  return 0 ;
}