Cod sursa(job #226297)

Utilizator drag0shSandulescu Dragos drag0sh Data 1 decembrie 2008 13:40:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>
#include <bitset>
using namespace std;

FILE *f=fopen("dfs.in","r"),*g=fopen("dfs.out","w");

long int n,m;
bitset  <100001>viz;

struct nod{
  long int info;
  nod* adr_urm;
};

nod *a[100001];

void adaug(nod* &v,int nr){
  nod* c=new nod;
  c->info=nr;
  c->adr_urm=v;
  v=c;
}


void citire(){
  long int i,x,y;
  fscanf(f,"%ld %ld",&n,&m);
  for(i=0;i<m;++i){
    fscanf(f,"%ld %ld",&x,&y);
    adaug(a[x],y);
    adaug(a[y],x);
  }
}

void dfs(long int k){
  viz[k]=1;
  nod* c=a[k];
  while(c){
    if(!viz[c->info])dfs(c->info);
    c=c->adr_urm;
  }
  
}

int main(){
  long i,contor;
  contor=0;
  citire();
 for(i=1;i<=n;i++){
   if(!viz[i])dfs(i),++contor;
  }
  fprintf(g,"%ld",contor);

  fclose(f);
  fclose(g);
  return 0;
}