Cod sursa(job #2175989)

Utilizator preda.andreiPreda Andrei preda.andrei Data 16 martie 2018 20:20:02
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

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

using Graph = vector<Node>;
using Component = vector<int>;
using Stack = stack<pair<int, int>>;

Component ExtractComponent(Graph &g, Stack &st, int end)
{
  Component comp;
  while (st.top().first != end) {
    comp.push_back(st.top().second);
    st.pop();
  }
  comp.push_back(st.top().first);
  comp.push_back(st.top().second);
  st.pop();
  return comp;
}

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

  for (const auto &next : g[node].next) {
    if (g[next].time == 0) {
      st.push({node, next});
      Dfs(g, st, next, comps);

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

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

int main()
{
  ifstream fin("biconex.in");
  ofstream fout("biconex.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);
    graph[b - 1].next.push_back(a - 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;
}