Cod sursa(job #1833683)

Utilizator TincaMateiTinca Matei TincaMatei Data 22 decembrie 2016 21:59:12
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.57 kb
#include <cstdio>
#include <ctype.h>

class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch() {
        ++sp;
        if (sp == 4096) {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser& operator >> (int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser& operator >> (long long &n) {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
}fin("ctc.in");


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) {
  ++ind;
  low[node] = index[node] = 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;
  fin >> n >> m;
  for(int i = 1; i <= m; ++i) {
    fin >> a >> b;
    mc[i] = b;
    next[i] = last[a];
    last[a] = i;
  }
  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;
}
//problema e completa cand e bagata si parsarea