Cod sursa(job #2277405)

Utilizator vladisimovlad coneschi vladisimo Data 6 noiembrie 2018 09:46:27
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <cstdio>
#include <set>
#include <stack>
#include <vector>

const int MAX_N = 1e5;

int lowlink[2 + MAX_N], index[2 + MAX_N], count, global;

bool inStack[2 + MAX_N];

std::vector<int> neighbours[2 + MAX_N];

std::set<int> sol[2 + MAX_N];

std::stack<int> nodes;

void connect(int u) {
  index[u] = count;
  lowlink[u] = count;
  inStack[u] = true;
  count++;
  nodes.push(u);
  for (int v : neighbours[u])
    if (index[v] == 0) {
      connect(v);
      lowlink[u] = std::min(lowlink[u], lowlink[v]);
    } else if (inStack[v])
      lowlink[u] = std::min(lowlink[u], index[v]);
  if (lowlink[u] == index[u]) {
    global++;
    int v;
    do {
      v = nodes.top();
      inStack[v] = false;
      sol[global].insert(v);
      nodes.pop();
    } while (v != u);
  }
}
int main() {
  freopen("ctc.in", "r", stdin);
  freopen("ctc.out", "w", stdout);
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    neighbours[u].push_back(v);
  }
  for (int u = 1; u <= n; u++)
    if (index[u] == 0)
      connect(u);
  printf("%d\n", global);
  for (int i = 1; i <= global; i++) {
    for (int j : sol[i])
      printf("%d ", j);
    printf("\n");
  }
  return 0;
}