Cod sursa(job #1166648)

Utilizator toranagahVlad Badelita toranagah Data 3 aprilie 2014 18:51:04
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <algorithm>
#include <bitset>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

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

#define len(x) int((x).size())

const int INF = 1 << 30;
const int MAX_N = 100100;

typedef vector<int> Graph[MAX_N];

int N, M;
Graph g, tg;
bitset<MAX_N> vis;
vector<vector<int>> ctc;

void kosaraju();
void dfs(int node, Graph g, vector<int> &st);

int main() {
  fin >> N >> M;
  for (int i = 1, a, b; i <= M; i += 1) {
    fin >> a >> b;
    g[a].push_back(b);
    tg[b].push_back(a);
  }
  kosaraju();

  fout << len(ctc) << '\n';
  for (auto i: ctc) {
    for (auto j: i) {
      fout << j << ' ';
    }
    fout << '\n';
  }
}

void kosaraju() {
  vector<int> tp;
  vis = 0;
  for (int i = 1; i <= N; i += 1)
    if (!vis[i]) dfs(i, g, tp);

  vis = 0;
  while (!tp.empty()) {
    int node = tp.back();
    tp.pop_back();

    if (vis[node]) continue;

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

void dfs(int node, Graph g, vector<int> &st) {
  vis[node] = 1;
  for (auto x: g[node])
    if (!vis[x]) dfs(x, g, st);
  st.push_back(node);
}