Cod sursa(job #1108314)

Utilizator andrei.sfrentSfrent Andrei andrei.sfrent Data 15 februarie 2014 16:15:22
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define MAXN 100001

int N, M;
vector<int> g[MAXN], gr[MAXN];
vector<vector<int>> components;
int seen[MAXN];
vector<int> top_sorted;

inline void init_seen() {
  memset(seen, 0, MAXN * sizeof(int));
}

void read() {
  scanf("%d%d", &N, &M);
  for(int i = 0; i < M; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    g[x].push_back(y);
    gr[y].push_back(x);
  }
}

void write() {
  printf("%zu\n", components.size());
  for(const vector<int>& c : components) {
    for(int x : c) {
      printf("%d ", x);
    }
    printf("\n");
  }
}

void dfs(int u) {
  seen[u] = 1;
  for(int v : g[u])
    if(!seen[v])
      dfs(v);
  top_sorted.push_back(u);
}

void forward() {
  for(int u = 1; u <= N; ++u)
    if(!seen[u])
      dfs(u);
}

void dfsr(int u) {
  seen[u] = 1;
  components.back().push_back(u);
  for(int v : gr[u])
    if(!seen[v])
      dfsr(v);
}

void backwards() {
  for(auto rit = top_sorted.rbegin(); rit != top_sorted.rend(); ++rit) {
    if(!seen[*rit]) {
      components.push_back(vector<int>());
      dfsr(*rit);
    }
  }
}

void kosaraju() {
  init_seen();
  forward();
  init_seen();
  backwards();
}

int main(int argc, char *argv[]) {
  freopen("ctc.in", "r", stdin);
  freopen("ctc.out", "w", stdout);

  read();
  kosaraju();
  write();

  return 0;
}