Cod sursa(job #2081636)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 4 decembrie 2017 21:54:59
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cstdio>
#include <vector>

const int MAXN = 1e5;

std::vector <int> g[MAXN + 1], con;
std::vector <std::vector <int> > ctc;
int d[MAXN + 1], idx[MAXN + 1], 
    st[MAXN + 1], top, lidx;
bool inst[MAXN + 1];

static inline int min(int a, int b) {
  return a > b ? b : a;
} 

void tarjan(int u) {
  st[top++] = u;
  inst[u] = 1;
  d[u] = idx[u] = lidx++;
  for (auto v: g[u]) {
    if (!idx[v]) {
      tarjan(v);
    }
    if (inst[v]) {
      d[u] = min(d[u], d[v]);
    }
  }
  if (d[u] == idx[u]) {
    int v;
    con.clear();
    do {
      v = st[--top];
      inst[v] = 0;
      con.push_back(v);
    } while (u != v);
    ctc.push_back(con);
  }
}

int main() {
  int n, m, u, v;
  FILE *f = fopen("ctc.in", "r");
  fscanf(f, "%d%d", &n, &m);
  for (int i = 0; i < m; ++i) {
    fscanf(f, "%d%d", &u, &v);
    g[u].push_back(v);
  }
  fclose(f);
  lidx = 1;
  for (int i = 1; i <= n; ++i) {
    if (!idx[i]) {
      tarjan(i);
    }
  }
  f = fopen("ctc.out", "w");
  fprintf(f, "%d\n", ctc.size());
  for (int i = 0; i < ctc.size(); ++i) {
    for (int j = 0; j < ctc[i].size(); ++j) {
      fprintf(f, "%d ", ctc[i][j]); 
    }
    fprintf(f, "\n");
  }
  fclose(f);
  return 0;
}