Cod sursa(job #1480560)

Utilizator stoianmihailStoian Mihail stoianmihail Data 2 septembrie 2015 19:23:30
Problema Componente biconexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 3.34 kb
#include <stdio.h>
#include <stdlib.h>

#define Smerenie 400001
#define Nadejde 100001

typedef struct {
  int v, next;
} list;

typedef struct {
  int u, v;
} cell;


int N, M, ss;
int buff = 1;
int d[Nadejde];
int low[Nadejde];
int adj[Nadejde];
list l[Smerenie];
list com[Smerenie];
cell stack[Smerenie];
int numSeen, adjb[Nadejde];
int freq[Nadejde], *bcc[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;
}

/** Adauga-l pe "u" la componenta curenta. **/
void put(int u) {
  com[buff].v = u;
  com[buff].next = adjb[numSeen];
  adjb[numSeen] = buff++;
}

/** Pune in stiva muchia (u, v). **/
void push(int u, int v) {
  stack[ss].u = u;
  stack[ss++].v = v;
}

/** Formeaza componenta curenta. **/
void getBcc(int u, int v) {
  cell tmp;
  numSeen++;
  do {
    tmp = stack[--ss];
    freq[numSeen] += 2;
    put(tmp.u), put(tmp.v);
  } while ((u != tmp.u) || (v != tmp.v));
}

/** Exploreaza graful, determinand componentele biconexe. **/
void dfs(int u, int parent, int depth) {
  int v, pos;
  low[u] = d[u] = depth;
  for (pos = adj[u]; pos; pos = l[pos].next) {
    v = l[pos].v;
    if (v != parent) {
      if (!d[v]) {
        push(u, v);
        dfs(v, u, depth + 1);
        if (low[v] < low[u]) {
          low[u] = low[v];
        }
        if (low[v] >= d[u]) {
          getBcc(u, v);
        }
      } else if (d[v] < low[u]) {
        low[u] = d[v];
      }
    }
  }
}

/** Aloca un vector de marimea "size" pentru componenta curenta. **/
void alloc(int *size) {
  bcc[buff] = (int*)calloc(*size, sizeof(int));
  (*size) = 0;
}

/** Sorteaza crescator nodurile din componenta curenta. **/
void sort(int begin, int end) {
  int b = begin, e = end, pivot = bcc[buff][(b + e) >> 1];
  while (b <= e) {
    while (bcc[buff][b] < pivot) {
      b++;
    }
    while (bcc[buff][e] > pivot) {
      e--;
    }
    if (b <= e) {
      int tmp = bcc[buff][b];
      bcc[buff][b++] = bcc[buff][e];
      bcc[buff][e--] = tmp;
    }
  }
  if (b < end) {
    sort(b, end);
  }
  if (begin < e) {
    sort(begin, e);
  }
}

/** Sterge dublurile din componenta. **/
void unique(int n) {
  int i = 0;
  sort(0, n - 1);
  while (i < n) {
    int j = i + 1;
    while ((j < n) && (bcc[buff][j] == bcc[buff][i])) {
      bcc[buff][j++] = 0;
    }
    i = j;
  }
}

/** Construieste componentele biconexe. **/
void biconex() {
  int pos;
  dfs(1, 0, 1);
  for (buff = 1; buff <= numSeen; buff++) {
    alloc(&freq[buff]);
    for (pos = adjb[buff]; pos; pos = com[pos].next) {
      bcc[buff][freq[buff]++] = com[pos].v;
    }
    unique(freq[buff]);
  }
}

int main(void) {
  int i, u, v;
  FILE *f = fopen("biconex.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("biconex.out", "w");

  biconex();

  fprintf(f, "%d\n", numSeen);
  for (u = 1; u <= numSeen; u++) {
    for (i = 0; i < freq[u]; i++) {
      if (bcc[u][i]) {
        fprintf(f, "%d ", bcc[u][i]);
      }
    }
    fputc('\n', f);
  }
  fclose(f);

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