Cod sursa(job #2220070)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 10 iulie 2018 14:37:32
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
/**
  *  Worg
  */
#include <stack>
#include <cstdio>
#include <vector>

FILE *fin = freopen("ctc.in", "r", stdin); FILE *fout = freopen("ctc.out", "w", stdout);

const int MAX_N = 1e5 + 5;

/*-------- Data --------*/
int n, m;
std::vector<std::vector<int > > graph;

int cursor;
int index[MAX_N], lowlink[MAX_N], inStack[MAX_N];
std::stack<int > stk;

std::vector<std::vector<int > > sccList;
/*-------- --------*/

void ReadInput() {
  scanf("%d%d", &n, &m); graph.resize(n + 1);

  for(int i = 0; i < m; i++) {
    int u, v; scanf("%d%d", &u, &v);

    graph[u].push_back(v);
  }
}

void StrongConnect(int node) {
  cursor++; index[node] = lowlink[node] = cursor;
  stk.push(node); inStack[node] = true;

  for(auto& nxt : graph[node]) {
    if(!index[nxt]) {
      StrongConnect(nxt);
      lowlink[node] = std::min(lowlink[node], lowlink[nxt]);
    } else if(inStack[node]) {
      lowlink[node] = std::min(lowlink[node], index[nxt]);
    }
  }

  //  Check if the current node is the "starting point" of a new strongly connected component
  if(index[node] == lowlink[node]) {
    std::vector<int > currentScc;

    int aux;
    do {
      aux = stk.top(); stk.pop(); inStack[aux] = false;
      currentScc.push_back(aux);
    }while(aux != node);

    sccList.push_back(currentScc);
  }
}

void Tarjan() {
  for(int node = 1; node <= n; node++) {
    if(!index[node]) {
      StrongConnect(node);
    }
  } 
}

void WriteOutput() {
  printf("%d\n", (int)sccList.size());

  for(auto& scc : sccList) {
    for(auto& node : scc) {
      printf("%d ", node);
    }
    printf("\n");
  }
}

int main() {
  ReadInput();

  Tarjan();

  WriteOutput();
  return 0;
}