Cod sursa(job #1757202)

Utilizator crushackPopescu Silviu crushack Data 14 septembrie 2016 17:52:54
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <algorithm>
#include <fstream>
#include <functional>
#include <stack>
#include <vector>

using namespace std;

vector<vector<int>> tarjan(const vector<vector<int>>& graph) {
  vector<vector<int>> ans;
  vector<bool> in_stack(graph.size());
  vector<int> idx(graph.size(), -1);
  vector<int> lowlink(graph.size());
  stack<int> st;
  int index = 0;

  function<void(int)> dfs;
  dfs = [&](int node) -> void {
    idx[node] = lowlink[node] = index++;
    st.push(node);
    in_stack[node] = true;

    for (int n : graph[node]) {
      if (idx[n] == -1) {
        dfs(n);
        lowlink[node] = min(lowlink[node], lowlink[n]);
      } else if (in_stack[n]) {
        lowlink[node] = min(lowlink[node], lowlink[n]);
      }
    }

    if (idx[node] == lowlink[node]) {
      vector<int> con;
      int n;
      do {
        con.push_back(n = st.top());
        st.pop();
        in_stack[n] = false;
      } while (n != node);
      ans.push_back(con);
    }
  };

  for (int i = 1; i < (int) graph.size(); ++ i) if (idx[i] == -1)
    dfs(i);

  return ans;
}

int main() {
  vector<vector<int>> graph;
  ifstream fin("ctc.in");
  ofstream fout("ctc.out");
  int n, m;

  fin >> n >> m;
  graph.resize(n + 1);
  for (int iter = 0; iter < m; ++iter) {
    int x, y;
    fin >> x >> y;
    graph[x].push_back(y);
  }

  auto ans = tarjan(graph);

  fout << ans.size() << "\n";
  for (auto comp : ans) {
    for (int elem : comp) {
      fout << elem << " ";
    }
    fout << "\n";
  }

  return 0;
}