Cod sursa(job #2015965)

Utilizator preda.andreiPreda Andrei preda.andrei Data 28 august 2017 11:58:08
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

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

using Graph = vector<Node>;

vector<int> Extract(stack<pair<int, int>> &st, const pair<int, int> &last_edge)
{
  vector<int> comp;
  while (st.top() != last_edge) {
    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, int node, stack<pair<int, int>> &st, vector<vector<int>> &comps)
{
  static int time = 0;
  g[node].time = g[node].low = ++time;

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

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

vector<vector<int>> FindComponents(Graph &g)
{
  vector<vector<int>> comps;
  for (size_t i = 0; i < g.size(); ++i) {
    if (g[i].time == 0) {
      stack<pair<int, int>> st;
      Dfs(g, i, st, 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 x, y;
    fin >> x >> y;
    graph[x - 1].edges.push_back(y - 1);
    graph[y - 1].edges.push_back(x - 1);
  }

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

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