Cod sursa(job #2690819)

Utilizator retrogradLucian Bicsi retrograd Data 26 decembrie 2020 02:17:21
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <bits/stdc++.h>

using namespace std;

template<typename Graph, typename CB>
void BCC(Graph& graph, CB cb) {
  int timer = 0, n = graph.size();
  vector<int> enter(n, -1);
  vector<tuple<int, int, int>> stk, comp;

  function<int(int, int)> dfs = [&](int node, int pei) {
    enter[node] = timer++;
    int ret = enter[node];
    
    for (auto itr : graph[node]) {
      int vec, ei; tie(vec, ei) = itr;
      if (ei == pei) continue;
      if (enter[vec] != -1) {
        ret = min(ret, enter[vec]);
        if (enter[vec] < enter[node])
          stk.emplace_back(node, vec, ei);
      } else {
        int sz = stk.size(), low = dfs(vec, ei);
        ret = min(ret, low);
        stk.emplace_back(node, vec, ei);
        if (low >= enter[node]) {
          comp = {stk.begin() + sz, stk.end()}; 
          cb(comp); stk.resize(sz);
        }
      }
    }
    return ret;
  };
  for (int i = 0; i < (int)graph.size(); ++i)
    if (enter[i] == -1) 
      dfs(i, -1);
}


int main() {
  ifstream cin("biconex.in");
  ofstream cout("biconex.out");
  int n, m; cin >> n >> m;
  vector<vector<pair<int, int>>> graph(n);
  for (int i = 0; i < m; ++i) {
    int a, b; cin >> a >> b; --a; --b;
    graph[a].emplace_back(b, i);
    graph[b].emplace_back(a, i);
  }
  vector<vector<int>> comps;
  BCC(graph, [&](vector<tuple<int, int, int>> comp) {
    vector<int> v;
    for (auto itr : comp) {
      int a, b; tie(a, b, ignore) = itr;
      v.push_back(a), v.push_back(b);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    comps.emplace_back(move(v));
  });
  cout << comps.size() << '\n';
  for (auto comp : comps) {
    for (auto x : comp) 
      cout << x + 1 << " ";
    cout << '\n';
  }
  return 0;
}