Cod sursa(job #1833681)

Utilizator TincaMateiTinca Matei TincaMatei Data 22 decembrie 2016 21:55:16
Problema Componente tare conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <cstdio>

const int MAX_N = 100000;
const int MAX_M = 200000;
int last[1+MAX_N], next[1+MAX_M], mc[1+MAX_M], index[1+MAX_N], low[1+MAX_N];
int st[MAX_N], top;
int ind, comp;
int sol[1+MAX_N], topS;
bool inSt[1+MAX_N];

int min(int a, int b) {
  if(a < b)
    return a;
  return b;
}

void ctc(int node) {
  low[node] = index[node] = ind;
  ++ind;
  st[top] = node; ++top;
  inSt[node] = true;

  int i = last[node];
  while(i != 0) {
    if(index[mc[i]] == 0) {
      ctc(mc[i]);
      low[node] = min(low[node], low[mc[i]]);
    } else if(inSt[mc[i]])
      low[node] = min(low[node], low[mc[i]]);
    i = next[i];
  }

  if(index[node] == low[node]) {
    comp++;
    while(st[top - 1] != node) {
      sol[topS] = st[top - 1];
      low[st[top - 1]] = low[node];
      inSt[st[top - 1]] = false; ++topS;
      --top;
    }
    inSt[node] = false;
    --top;
    sol[topS] = node; ++topS;
  }
}

int main() {
  int n, m, a, b, c;
  FILE *fin = fopen("ctc.in", "r");
  fscanf(fin, "%d%d", &n, &m);
  for(int i = 1; i <= m; ++i) {
    fscanf(fin, "%d%d", &a, &b);
    mc[i] = b;
    next[i] = last[a];
    last[a] = i;
  }
  fclose(fin);
  for(int i = 1; i <= n; ++i)
    if(index[i] == 0)
      ctc(i);
  FILE *fout = fopen("ctc.out", "w");
  fprintf(fout, "%d\n", comp);
  c = low[sol[0]];
  for(int i = 0; i < n; ++i) {
    if(low[sol[i]] != c) {
      c = low[sol[i]];
      fprintf(fout, "\n");
    }
    fprintf(fout, "%d ", sol[i]);
  }
  fclose(fout);
  return 0;
}