Cod sursa(job #1711725)

Utilizator stoianmihailStoian Mihail stoianmihail Data 1 iunie 2016 00:38:39
Problema Componente tare conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <stdio.h>
#include <stdlib.h>

#define Smerenie 200000
#define Nadejde 100000

typedef struct {
  int v, next;
} list;

int N, M;
int d[Nadejde + 1];

int adj[Nadejde + 1];
list l[Smerenie + 1];

int ss, stack[Nadejde + 1];
char onStack[Nadejde + 1];

int numScc;
int size[Nadejde + 1];
int *scc[Nadejde + 1];

int MIN(int X, int Y) {
  return X < Y ? X : Y;
}

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

int tarjan(int u, int depth) {
  d[u] = depth;
  stack[ss++] = u;
  onStack[u] = true;

  int pos, v;
  for (pos = adj[u]; pos; pos = l[pos].next) {
    v = l[pos].v;
    if (d[v] == 0) {
      d[u] = MIN(d[u], tarjan(v, depth + 1));
    } else if (onStack[v]) {
      d[u] = MIN(d[u], d[v]);
    }
  }

  if (d[u] == depth) {
    int save = ss;
    do {
      ss--;
    } while (stack[ss] != u);
    size[numScc] = save - ss;
    scc[numScc] = (int*)calloc(size[numScc], sizeof(int));
    
    int ptr = 0;
    ss = save;
    do {
      v = stack[--ss];
      onStack[v] = false;
      scc[numScc][ptr++] = v;
    } while (v != u);
    numScc++;
  }
  return d[u];
}

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

  int i, u, v;
  fscanf(f, "%d %d", &N, &M);
  while (M) {
    fscanf(f, "%d %d", &u, &v);
    addEdge(u, v, M);
    M--;
  }
  fclose(f);

  for (u = 1; u <= N; u++) {
    if (d[u] == 0) {
      tarjan(u, 1);
    }
  }

  freopen("ctc.out", "w", stdout);
  fprintf(stdout, "%d\n", numScc);
  for (i = 0; i < numScc; i++) {
    for (u = 0; u < size[i]; u++) {
      fprintf(stdout, " %d", scc[i][u]);
    }
    fprintf(stdout, "\n");
  }
  fclose(stdout);

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