Cod sursa(job #3203030)

Utilizator rastervcrastervc rastervc Data 12 februarie 2024 23:11:30
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

inline void setup_io() {
  freopen("ctc.in", "r", stdin);
  freopen("ctc.out", "w", stdout);
}

template <typename T>
using vec = vector<T>;

class Graph {
  vec<vec<int>> adj, scc;
  vec<bool> processed;
  vec<int> tin;
  stack<int> st;
  int N, timer;
  
  int dfs(int u) {
    int low = tin[u] = ++timer;
    st.push(u);
    for (int v : adj[u])
      if (!processed[v])
        low = min(low, tin[v] ?: dfs(v));
    if (low == tin[u]) {
      scc.emplace_back();
      for (; st.top() != u; st.pop()) {
        scc.back().push_back(st.top());
        processed[st.top()] = true;
      }
      processed[u] = true;
      scc.back().push_back(u);
      st.pop();
    }
    return low;
  }

public:
  Graph(int N) : N(N), adj(N), tin(N), processed(N) {}

  void add_edge(int u, int v) {
    adj[u].push_back(v);
  }

  vec<vec<int>> strongly_connected_components() {
    fill(tin.begin(), tin.end(), 0);
    fill(processed.begin(), processed.end(), false);
    scc.clear();
    timer = 0;
    for (int u = 0; u < N; ++u)
      if (!tin[u]) dfs(u);
    // strongly connected components in topological order
    reverse(scc.begin(), scc.end());
    return scc;
  }
};

int main() {
  setup_io();
  
  int N, M, u, v;
  cin >> N >> M;
  Graph graph(N);
  for (int i = 0; i < M; ++i) {
    cin >> u >> v;
    graph.add_edge(u - 1, v - 1);
  }
  
  auto scc = graph.strongly_connected_components();

  cout << scc.size() << '\n';
  for (const vec<int> &comp : scc) {
    for (int u : comp) cout << u + 1 << ' ';
    cout << '\n';
  }

  return 0;
}