Cod sursa(job #2456610)

Utilizator tudi98Cozma Tudor tudi98 Data 14 septembrie 2019 20:50:05
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> G[100005];
int cidx = 0;
int idx[100005], low[100005];
stack<int> S;
bool in_stack[100005];

vector<vector<int>> scc;

void tarjan(int node) {
  idx[node] = ++cidx;
  low[node] = cidx;
  in_stack[node] = 1;
  S.push(node);

  for (auto p : G[node]) {
    if (!idx[p]) {
      tarjan(p);
      low[node] = min(low[node], low[p]);
    } else if (in_stack[p]) {
      low[node] = min(low[node], idx[p]);
    }
  }

  if (low[node] == idx[node]) {
    int u;
    scc.push_back(vector<int>());
    do {
      u = S.top();
      S.pop();
      in_stack[u] = 0;
      scc.back().push_back(u);
    } while (u != node);
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  ifstream cin("ctc.in");
  ofstream cout("ctc.out");

  cin >> n >> m;
  int x, y;
  while (m--) {
    cin >> x >> y;
    G[x].push_back(y);
  }

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

  cout << scc.size() << "\n";
  for (auto v : scc) {
    for (auto i : v) cout << i << " ";
    cout << "\n";
  }
}