Cod sursa(job #2175734)

Utilizator preda.andreiPreda Andrei preda.andrei Data 16 martie 2018 18:43:17
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <fstream>
#include <vector>

using namespace std;

struct Node
{
  bool visited = false;
  vector<int> next;
};

using Graph = vector<Node>;
using Component = vector<int>;

void Dfs(Graph &g, int node, vector<int> &order)
{
  g[node].visited = true;
  for (const auto &next : g[node].next) {
    if (!g[next].visited) {
      Dfs(g, next, order);
    }
  }
  order.push_back(node);
}

vector<int> GetOrder(Graph &g)
{
  vector<int> order;
  for (size_t i = 0; i < g.size(); ++i) {
    if (!g[i].visited) {
      Dfs(g, i, order);
    }
  }
  return order;
}

void ExtractComponent(Graph &g, int node, Component &comp)
{
  comp.push_back(node);
  g[node].visited = true;

  for (const auto &next : g[node].next) {
    if (!g[next].visited) {
      ExtractComponent(g, next, comp);
    }
  }
}

vector<Component> GetComponents(Graph &g, const vector<int> &order)
{
  vector<Component> comps;
  for (int i = order.size() - 1; i >= 0; --i) {
    auto node = order[i];
    if (!g[node].visited) {
      comps.push_back({});
      ExtractComponent(g, node, comps.back());
    }
  }
  return comps;
}

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

  int nodes, edges;
  fin >> nodes >> edges;

  Graph graph(nodes);
  Graph rev(nodes);

  for (int i = 0; i < edges; ++i) {
    int a, b;
    fin >> a >> b;
    graph[a - 1].next.push_back(b - 1);
    rev[b - 1].next.push_back(a - 1);
  }

  auto order = GetOrder(graph);
  auto comps = GetComponents(rev, order);

  fout << comps.size() << "\n";
  for (const auto &comp : comps) {
    for (const auto &node : comp) {
      fout << node + 1 << " ";
    }
    fout << "\n";
  }

  return 0;
}