Cod sursa(job #1399874)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 24 martie 2015 22:57:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <stdio.h>

#define MAX_N 100000
#define MAX_M 200000
#define NIL -1

typedef struct {
  int v, next;
} cell;

cell l[2 * MAX_M];
int adj[MAX_N];
bool d[MAX_N];

void addEdge(int u, int v, int pos) {
  l[pos].v = v;
  l[pos].next = adj[u];
  adj[u] = pos;
}
void dfs(int u) {
  d[u] = 1;

  for (int pos = adj[u]; pos != NIL; pos = l[pos].next) {
    int v = l[pos].v;
    if (!d[v]) {
      dfs(v);
    }
  }
}
int main (void) {
  FILE *f;
  int n, m;
  int u, v;
  int ans;

  f = fopen("dfs.in", "r");
  fscanf(f, "%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    adj[i] = NIL;
  }
  for (int i = 0; i < m; ++i) {
    fscanf(f, "%d%d", &u, &v);
    addEdge(u - 1, v - 1, 2 * i);
    addEdge(v - 1, u - 1, 2 * i + 1);
  }
  fclose(f);

  ans = 0;
  for (int i = 0; i < n; ++i) {
    if (!d[i]) {
      ++ans;
      dfs(i);
    }
  }

  f = fopen("dfs.out", "w");
  fprintf(f, "%d\n", ans);
  fclose(f);
  return 0;
}