Cod sursa(job #2227888)

Utilizator inquisitorAnders inquisitor Data 2 august 2018 10:04:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
///by mihail stoian

#include <stdio.h>
#include <ctype.h>

#define Nadejde 100000
#define Dragoste 4096

int N, M;
int boss[Nadejde + 1];
int set[Nadejde / 32 + 1];

char buff[Dragoste];
int pos = Dragoste;

char getChar(FILE *f) {
  if (pos == Dragoste) {
    fread(buff, 1, Dragoste, f);
    pos = 0;
  }
  return buff[pos++];
}

int freef(FILE *f) {
  int result = 0;
  char c;

  do {
    c = getChar(f);
  } while (!isdigit(c));
  do {
    result = (result << 3) + (result << 1) + c - '0';
    c = getChar(f);
  } while (isdigit(c));
  return result;
}

void init() {
  int u;

  for (u = 1; u <= Nadejde; u++) {
    boss[u] = u;
  }
}

int find(int u) {
  int r = u, tmp;

  while (r != boss[r]) {
    r = boss[r];
  }
  while (u != boss[u]) {
    tmp = boss[u];
    boss[u] = r;
    u = tmp;
  }
  return r;
}

void unify(int u, int v) {
  u = find(u);
  v = find(v);

  if (u != v) {
    boss[v] = u;
  }
}

int getBit(int x) {
  return (set[x >> 5] >> (x & 31)) & 1;
}

void setBit(int x) {
  set[x >> 5] |= 1 << (x & 31);
}

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

  /* Initializarea datelor. */
  init();

  /* Citirea datelor. */
  N = freef(f);
  for (M = freef(f); M; M--) {
    unify(freef(f), freef(f));
  }
  fclose(f);

  /* Calcularea solutiei. */
  int u, v, count = 0;
  for (u = 1; u <= N; u++) {
    v = find(u);
    if (!getBit(v)) {
      setBit(v);
      count++;
    }
  }

  /* Afisarea solutiei. */
  freopen("dfs.out", "w", stdout);
  fprintf(stdout, "%d\n", count);
  fclose(stdout);

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