Cod sursa(job #1414018)

Utilizator toranagahVlad Badelita toranagah Data 2 aprilie 2015 11:49:13
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 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 pb push_back
typedef vector<vector<int>> VVI;

int N, M;
VVI g, tg;
VVI sccs;

void dfs(int node, VVI &g, vector<bool> &vis, vector<int> &st) {
  vis[node] = 1;
  for (auto v: g[node]) {
    if (!vis[v]) dfs(v, g, 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, g, vis, ts);
  }

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

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

    if (vis[node]) continue;

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

}

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

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

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