Cod sursa(job #2741076)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 15 aprilie 2021 14:44:09
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

const int NMAX = 1e5;

std::vector<int> graph[1 + NMAX];
std::vector<int> transposed_graph[1 + NMAX];

std::vector<int> list;

bool vis[1 + NMAX];

std::vector<std::vector<int>> scc;

void dfs(int node) {
  vis[node] = true;

  for (int nb: graph[node]) {
    if (!vis[nb])
      dfs(nb);
  }

  list.push_back(node);
}

void dfs_transposed(int node) {
  vis[node] = true;

  for (int nb: transposed_graph[node]) {
    if (!vis[nb])
      dfs_transposed(nb);
  }

  scc.back().push_back(node);
}

int main() {
  std::ifstream in("ctc.in");
  std::ofstream out("ctc.out");

  int n, m;
  in >> n >> m;

  for (int i = 1; i <= m; ++i) {
    int a, b;
    in >> a >> b;

    graph[a].push_back(b);
    transposed_graph[b].push_back(a);
  }

  for (int i = 1; i <= n; ++i) {
    if (!vis[i])
      dfs(i);
  }

  memset(vis, 0, sizeof(vis));
  for (int i = (int)list.size() - 1; i >= 0; --i) {
    if (!vis[list[i]]) {
      scc.emplace_back();
      dfs_transposed(list[i]);
    }
  }

  out << scc.size() << '\n';
  for (auto& comp: scc) {
    for (auto& i: comp)
      out << i << ' ';
    out << '\n';
  }

  return 0;
}