Cod sursa(job #1265642)

Utilizator cella.florescuCella Florescu cella.florescu Data 17 noiembrie 2014 15:35:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.78 kb
#include <stdio.h>
#include <stdlib.h>
int lst[100001], vf[200001], urm[200001], m, viz[100001];

void adauga(int x, int y){
  vf[++m]=y;
  urm[m]=lst[x];
  lst[x]=m;
}

void parDfs(int x){
  int p, y;
  viz[x]=1;
  p=lst[x];
  while(p){
    y=vf[p];
    if(!viz[y])
      parDfs(y);
    p=urm[p];
  }
}

int main()
{
    FILE *fin, *fout;
    int N, M, x, y, i, conexe;
    fin=fopen("dfs.in", "r");
    fscanf(fin, "%d%d", &N, &M);
    for(i=0; i<M; i++){
      fscanf(fin, "%d%d", &x, &y);
      adauga(x, y); adauga(y, x);
    }
    fclose(fin);
    conexe=0;
    for(i=1; i<=N; i++)
      if(!viz[i]){
        ++conexe;
        parDfs(i);
      }
    fout=fopen("dfs.out", "w");
    fprintf(fout, "%d\n", conexe);
    fclose(fout);
    return 0;
}