Cod sursa(job #2076168)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 26 noiembrie 2017 11:52:24
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

const int MAX_N = 100000;

std::vector<int> g[1 + MAX_N];
std::vector<int> rev[1 + MAX_N];
std::vector<int> scc[1 + MAX_N];
bool viz[1 + MAX_N];
std::vector<int> topo;

void dfs(int node) {
  viz[node] = true;
  for (auto u : g[node]) {
    if (!viz[u]) {
      dfs(u);
    }
  }
  topo.push_back(node);
}

int k;

void makeScc(int node) {
  viz[node] = true;
  scc[k].push_back(node);
  for (auto u : rev[node]) {
    if (!viz[u]) {
      makeScc(u);
    }
  }
}

int main() {
  freopen("ctc.in", "r", stdin);
  freopen("ctc.out", "w", stdout);

  int N, M;
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= M; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    g[x].push_back(y);
    rev[y].push_back(x);
  }
  for (int i = 1; i <= N; i++) {
    if (!viz[i]) {
      dfs(i);
    }
    viz[i] = false;
  }
  std::reverse(topo.begin(), topo.end());
  for (int i = 0; i < N; i++) {
    if (!viz[topo[i]]) {
      k++;
      makeScc(topo[i]);
    }
    //printf("%d ", topo[i]);
  }
  //printf("\n");
  printf("%d\n", k);
  for (int i = 1; i <= k; i++) {
    for (auto node : scc[i]) {
      printf("%d ", node);
    }
    printf("\n");
  }
  return 0;
}