Cod sursa(job #2121791)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 4 februarie 2018 12:45:00
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <stack>
#include <bitset>
#include <vector>

using namespace std;

const int MAXN = 100005;

ifstream input("ctc.in");
ofstream output("ctc.out");

vector<int> graph[MAXN];
vector<vector<int>> components;
stack<int> st;
bitset<MAXN> inStack;
int n, m, index[MAXN], lowlink[MAXN], INDEX;

void readData() {
  input >> n >> m;
  int x, y;
  for (int i = 0; i < m; i++) {
    input >> x >> y;
    graph[x].push_back(y);
  }
}

void dfs(int node) {
  index[node] = lowlink[node] = ++INDEX;
  st.push(node);
  inStack[node] = 1;

  for (int y : graph[node]) {
    if (!index[y]) {
      dfs(y);
      lowlink[node] = min(lowlink[node], lowlink[y]);
    } else if (inStack[y]) {
      lowlink[node] = min(lowlink[node], index[y]);
    }
  }

  if (lowlink[node] == index[node]) {
    int y;
    vector<int> comp;
    do {
      y = st.top();
      st.pop();
      comp.push_back(y);
    } while (y != node);
    components.push_back(comp);
  }
}

void tarjan() {
  for (int i = 1; i <= n; i++)
    if (!index[i]) {
      dfs(i);
    }
}

void printComponents() {
  output << components.size() << '\n';
  for (auto c : components) {
    for (int node : c)
      output << node << ' ';
    output << '\n';
  }
}

int main() {
  readData();
  tarjan();
  printComponents();
  return 0;
}