Cod sursa(job #1461249)

Utilizator hrazvanHarsan Razvan hrazvan Data 15 iulie 2015 11:10:45
Problema Componente tare conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.51 kb
#include <stdio.h>
#define MAXN 100000
#define MAXM 200000
int no = 0;
int nod[2 * MAXM], next[2 * MAXM], ult[MAXN];
int urm[MAXN], prim[MAXN], nr = 0;
int stiv[MAXN], dr = 0, lo[MAXN], val[MAXN];
char pest[MAXN];

inline int min2(int a, int b){
  return a < b ? a : b;
}

void caut(int x){
  stiv[dr] = x;
  dr++;
  pest[x] = 1;
  lo[x] = val[x] = no;
  no++;
  int poz = ult[x];
  while(poz != -1){
    if(val[nod[poz]] == -1)
       caut(nod[poz]);
    if(pest[nod[poz]])
      lo[x] = min2(lo[x], lo[nod[poz]]);
    poz = next[poz];
  }
  int last, k;
  if(lo[x] == val[x]){
    prim[nr] = stiv[dr - 1];
    last = stiv[dr - 1];
    dr--;
    while(last != x){
      pest[last] = 0;
      k = stiv[dr - 1];
      urm[last] = k;
      last = k;
      dr--;
    }
    urm[x] = -1;
    pest[x] = 0;
    nr++;
  }
}

int main(){
  FILE *in = fopen("ctc.in", "r");
  int n, m, i, x, y, dr = 0;
  fscanf(in, "%d%d", &n, &m);
  for(i = 0; i < n; i++){
    ult[i] = -1;
    val[i] = -1;
  }
  for(i = 0; i < m; i++){
    fscanf(in, "%d%d", &x, &y);
    x--;  y--;
    nod[dr] = y;
    next[dr] = ult[x];
    ult[x] = dr;
    dr++;
  }
  fclose(in);
  for(i = 0; i < n; i++){
    if(val[i] == -1)
      caut(i);
  }
  FILE *out = fopen("ctc.out", "w");
  fprintf(out, "%d\n", nr);
  int p;
  for(i = 0; i < nr; i++){
    p = prim[i];
    while(p != -1){
      fprintf(out, "%d ", p + 1);
      p = urm[p];
    }
    fputc('\n', out);
  }
  fclose(out);
  return 0;
}