Cod sursa(job #235668)

Utilizator juniorOvidiu Rosca junior Data 25 decembrie 2008 07:10:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <stdio.h>

int n, m, viz[100005], ncc; // numarul de componente conexe

typedef struct Nod {
  int x;
  Nod *a;
};
Nod* v[100005];

void add (Nod* &dest, int val) {
  Nod* p;
  p = new Nod;
  p->x = val;
  p->a = dest;
  dest = p;
}

void citire () {
  freopen("dfs.in", "r", stdin);
  freopen("dfs.out", "w", stdout);
  scanf("%d %d", &n, &m);
  int i, x, y;

  for (i = 1; i <= m; i++) {
    scanf("%d %d", &x, &y);
    add(v[x], y);
    add(v[y], x);
  }
}

void df (int nod) {
  Nod* p;
  viz[nod] = 1;
  for (p = v[nod]; p != NULL; p = p->a)
    if (!viz[p->x])
      df(p->x);
}

int main () {
  citire();
  int i;
  for (i = 1; i <= n; i++)
    if (!viz[i]) {
      ncc++;
      df(i);
    }
  printf("%d\n",ncc);
  return 0;
}