Cod sursa(job #2435049)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 2 iulie 2019 20:52:02
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

struct Graph {
  int n, timer;
  vector<bool> in_stk;
  vector<int> in, low, stk;
  vector<vector<int>> adj, scc;
  Graph(int n_) : n(n_), timer(0), in_stk(n), in(n, -1), low(n, -1), adj(n) {
    stk.reserve(n);
  }
  void AddEdge(int u, int v) {
    adj[u].emplace_back(v);    
  }
  void Tarjan(int node) {
    in[node] = low[node] = ++timer;
    stk.emplace_back(node);
    in_stk[node] = true;
    for (int &x : adj[node]) {
      if (in[x] == -1) {
        Tarjan(x);
        low[node] = min(low[node], low[x]);
      } else if (in_stk[x]) {
        low[node] = min(low[node], low[x]);
      }
    }
    if (low[node] == in[node]) {
      int x;
      scc.emplace_back();
      do {
        x = stk.back();
        stk.pop_back();
        in_stk[x] = false;
        scc.back().emplace_back(x);
      } while (x != node);
    }
  }
  void FindSCC() {
    for (int i = 0; i < n; ++i) {
      if (in[i] == -1) {
        Tarjan(i);
      }
    }
  }
  vector<vector<int>> GetSCC() {
    return scc;
  }
};

int main() {
  ifstream cin("ctc.in");
  ofstream cout("ctc.out");

  int n, m; cin >> n >> m;
  Graph g(n);
  while (m--) {
    int u, v; cin >> u >> v;
    g.AddEdge(u - 1, v - 1);
  }
  g.FindSCC();
  auto scc = g.GetSCC();
  cout << scc.size() << endl;
  for (auto &comp : scc) {
    for (int &x : comp) {
      cout << x + 1 << ' ';
    }
    cout << '\n';
  }

  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}