Cod sursa(job #2175765)

Utilizator preda.andreiPreda Andrei preda.andrei Data 16 martie 2018 18:54:29
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

struct Node
{
  int time = 0;
  int low = 0;
  bool in_stack = false;
  vector<int> next;
};

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

Component ExtractComponent(Graph &g, stack<int> &st, int end)
{
  Component comp;
  do {
    comp.push_back(st.top());
    g[st.top()].in_stack = false;
    st.pop();
  } while (comp.back() != end);
  return comp;
}

void Tarjan(Graph &g, stack<int> &st, int node, vector<Component> &comps)
{
  static int time = 0;
  g[node].time = g[node].low = ++time;

  st.push(node);
  g[node].in_stack = true;

  for (const auto &next : g[node].next) {
    if (g[next].time == 0) {
      Tarjan(g, st, next, comps);
    }
    if (g[next].in_stack) {
      g[node].low = min(g[node].low, g[next].low);
    }
    g[node].low = min(g[node].low, g[next].time);
  }

  if (g[node].low >= g[node].time) {
    comps.push_back(ExtractComponent(g, st, node));
  }
  if (g[node].time == 1 && g[node].next.size() > 1) {
    comps.push_back(ExtractComponent(g, st, node));
  }
}

vector<Component> GetComponents(Graph &g)
{
  vector<Component> comps;
  for (size_t i = 0; i < g.size(); ++i) {
    if (g[i].time == 0) {
      stack<int> st;
      Tarjan(g, st, i, comps);
    }
  }
  return comps;
}

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

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

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

  auto comps = GetComponents(graph);
  fout << comps.size() << "\n";

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

  return 0;
}