Cod sursa(job #1480470)

Utilizator stoianmihailStoian Mihail stoianmihail Data 2 septembrie 2015 17:19:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.21 kb
#include <stdio.h>

#define Smerenie 200001
#define Nadejde 100001

typedef struct {
  int v, next;
} list;

int N, M;
int adj[Nadejde];  // capetele listelor de adiacenta.
list l[Smerenie];  // lista muchiilor alocata static.
char seen[Nadejde];

/** Adauga-l pe "v" la lista de adiacenta a lui "u". **/
void addEdge(int u, int v, int pos) {
  l[pos].v = v;
  l[pos].next = adj[u];
  adj[u] = pos;
}

/** Parcurge recursiv nodul "u". **/
void dfs(int u) {
  int pos;
  if (!seen[u]) {
    seen[u] = 1;
    for (pos = adj[u]; pos; pos = l[pos].next) {
      dfs(l[pos].v);
    }
  }
}

/** Afla numarul de componente conexe ale grafului. **/
int conex() {
  int u, count = 0;
  for (u = 1; u <= N; u++) {
    if (!seen[u]) {
      dfs(u);
      count++;
    }
  }
  return count;
}

int main(void) {
  int i, u, v;
  FILE *f = fopen("dfs.in", "r");

  /* Citeste graful. */
  fscanf(f, "%d %d", &N, &M);
  for (i = 1; i <= M; i++) {
    fscanf(f, "%d %d", &u, &v);
    addEdge(u, v, i);
    addEdge(v, u, i + M);
  }
  fclose(f);

  f = fopen("dfs.out", "w");

  fprintf(f, "%d\n", conex());
  fclose(f);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}