Cod sursa(job #2017334)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 31 august 2017 21:34:57
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>

const int MAX_N = 100000;

std::vector<int>G[1 + MAX_N];
std::vector<std::vector<int> >ctc;
std::stack<int>st;
int low[1 + MAX_N], lvl[1 + MAX_N];
bool viz[1 + MAX_N], inStiva[1 + MAX_N];
int order;

void dfs(int nod) {
  viz[nod] = true;
  low[nod] = lvl[nod] = ++order;
  inStiva[nod] = true;
  st.push(nod);
  for (auto it:G[nod]) {
    if (!viz[it])
      dfs(it);
    if (inStiva[it])
      low[nod] = std::min(low[nod], low[it]);
  }
  if (low[nod] == lvl[nod]) {
    std::vector<int>aux;
    int tmp;
    do {
      tmp = st.top();
      st.pop();
      inStiva[tmp] = false;
      aux.push_back(tmp);
    } while (tmp != nod);
    ctc.push_back(aux);
  }
}

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);
    G[u].push_back(v);
  }

  for (int i = 1; i <= n; ++i)
    if (!viz[i])
      dfs(i);

  printf("%d\n", ctc.size());
  for (auto it1:ctc) {
    for (auto it2:it1)
      printf("%d ", it2);
    printf("\n");
  }

  return 0;
}