Nu aveti permisiuni pentru a descarca fisierul grader_test15.ok

Cod sursa(job #147988)

Utilizator alecmanAchim Ioan Alexandru alecman Data 3 martie 2008 19:48:06
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include<stdio.h>
#include<string.h>

#define INPUT "dfs.in"
#define OUTPUT "dfs.out"
#define CL(x) memset(x,0,sizeof(x));

FILE *fin=fopen(INPUT, "r"),*fout=fopen(OUTPUT, "w");

typedef struct elem{
  long value;
  struct elem *next;
};

elem* p[100001];

long N,M;

int util[100001];

void readValues();

void solveFunction();

void DF(long);

int main(){
  readValues();
  solveFunction();
  fclose(fin);
  fclose(fout);
  return 0;
}

void readValues(){
  fscanf(fin, "%ld %ld", &N, &M);
  long val1,val2;
  elem *adr;
  for(long i=1;i<=M;++i){
    fscanf(fin, "%ld %ld", &val1, &val2);
    adr=new elem;
    adr->value=val2;
    adr->next=p[val1];
    p[val1]=adr;
    adr=new elem;
    adr->value=val1;
    adr->next=p[val2];
    p[val2]=adr;
  }
}

void solveFunction(){
  CL(util);
  long final=0;
  for(long i=1;i<=N;++i){
    if(!util[i]){
      ++final;
      DF(i);
    }
  }
  fprintf(fout, "%ld\n", final);
}

void DF(long poz){
  elem *adr;
  adr=p[poz];
  util[poz]=1;
  while(adr!=NULL){
    if(!util[adr->value])
      DF(adr->value);
    adr=adr->next;
  }
}