Cod sursa(job #1580933)

Utilizator toranagahVlad Badelita toranagah Data 26 ianuarie 2016 12:28:35
Problema Componente tare conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
//Problem kosaraju
#include <cassert>
#include <cmath>
#include <cstdint>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

#define cin fin
#define cout fout

#define pb push_back
typedef vector<vector<int>> VVI;

int N, M;
VVI graph;
VVI sccs;

void dfs(int node, VVI &graph, vector<bool> &vis, vector<int> &st) {
  vis[node] = 1;
  for (auto v: graph[node]) {
    if (!vis[v]) dfs(v, graph, vis, st);
  }
  st.push_back(node);
}

void kosaraju() {
  vector<int> ts;
  vector<bool> vis(N + 1, 0);

  for (int i = 1; i <= N; i += 1) {
    if (!vis[i]) dfs(i, graph, vis, ts);
  }

  fill(vis.begin(), vis.end(), 0);

  reverse(ts.begin(), ts.end());

  while (!ts.empty()) {
    int node = ts.back();
    ts.pop_back();

    if (vis[node]) continue;

    sccs.push_back(vector<int>());
    dfs(node, graph, vis, sccs.back());
  }

}

void readin() {
  cin >> N >> M;
  graph.resize(N + 1);
  for (int i = 1, a, b; i <= M; i += 1) {
    cin >> a >> b;
    graph[a].pb(b);
  }
}

void printout() {
  cout << sccs.size() << endl;
  for (auto c: sccs) {
    for (auto v: c) {
      cout << v << ' ';
    }
    cout << '\n';
  }
}

int main() {
  readin();
  kosaraju();
  printout();
  return 0;
}