Cod sursa(job #991220)

Utilizator toranagahVlad Badelita toranagah Data 30 august 2013 01:14:48
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

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

const int MAX_N = 100100;

int N, M;
vector<int> graph[MAX_N];
vector<int> transpose_graph[MAX_N];
vector<vector<int>> sccs;

void read_input();
void kosaraju();
void dfs(int node, vector<int> g[], vector<bool>& visited, vector<int>& st);
void print_output();


int main() {
  read_input();
  kosaraju();
  print_output();
  return 0;
}

void read_input() {
  fin >> N >> M;
  for (int i = 1, a, b; i <= M; ++i) {
    fin >> a >> b;
    graph[a].push_back(b);
    transpose_graph[b].push_back(a);
  }
}

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

  for (int i = 1; i <= N; ++i) {
    if (!visited[i]) dfs(i, graph, visited, sorted_nodes);
  }
  fill(visited.begin(), visited.end(), 0);

  while (!sorted_nodes.empty()) {
    int node = sorted_nodes.back();
    sorted_nodes.pop_back();
    if (visited[node]) continue;
    
    sccs.push_back(vector<int>());
    dfs(node, transpose_graph, visited, sccs.back());
  }
}

void dfs(int node, vector<int> g[], vector<bool>& visited, vector<int>& st) {
  visited[node] = true;

  for (auto x : g[node]) {
    if (!visited[x]) dfs(x, g, visited, st);
  }

  st.push_back(node);
}

void print_output() {
  fout << sccs.size() << '\n';
  for (auto scc : sccs) {
    for (auto node : scc) {
      fout << node << ' ';
    }
    fout << '\n';
  }
}