Cod sursa(job #146347)

Utilizator MciprianMMciprianM MciprianM Data 1 martie 2008 16:18:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<stdio.h>
using namespace std;
struct nod{
  int info;
  nod*urm;
};
nod *v[100001];
int viz[100001];
int n, m, cont;
FILE *fin, *fout;
void add(nod*&vf, int x){
  nod* p=new nod;
  p->info=x;
  p->urm=vf;
  vf=p;
}
void DF(int i){
  nod* p;
  p=v[i];
  viz[i]=1;
  while(p){
    if(!viz[p->info]){
      viz[p->info]=1;
      DF(p->info);
      }
    p=p->urm;
  }
}
int main(){
  int i,x,y;
  fin=fopen("dfs.in", "rt");
  fscanf(fin, "%d%d", &n, &m);
  for(i=0;i<m;i++){
    fscanf(fin, "%d%d", &x, &y);
    add(v[x],y);
    add(v[y],x);
  }
  fclose(fin);
  fout=fopen("dfs.out", "wt");
  for(i=1;i<=n;i++)
    if(!viz[i]){
      DF(i);
      cont++;
    }
  fprintf(fout, "%d\n", cont);
  fclose(fout);
  return 0;
}