Cod sursa(job #2227887)

Utilizator inquisitorAnders inquisitor Data 2 august 2018 10:02:24
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <stdio.h>
#include <ctype.h>

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

void init() {
  int u;

  for (u = 1; u <= 100000; 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");

  init();

  scanf("%d %d", &N, &M);
  for (; M; M--) {
    int x, y;

  scanf("%d %d", &x, &y);
    unify(x, y);
  }
  fclose(f);

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

  freopen("dfs.out", "w", stdout);
  fprintf(stdout, "%d\n", count);

  return 0;
}