Cod sursa(job #2681648)

Utilizator crucerucalinCalin-Cristian Cruceru crucerucalin Data 6 decembrie 2020 09:22:03
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>
#include <stack>
#include <unordered_set>
#include <vector>

using namespace std;

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

  int n, m;
  fin >> n >> m;

  vector<vector<int>> graph(n);
  for (auto i = 0; i < m; ++i) {
    int x, y;
    fin >> x >> y;
    graph[x - 1].emplace_back(y - 1);
    graph[y - 1].emplace_back(x - 1);
  }

  vector<int> indexes(n, -1);
  vector<int> lowlinks(n);
  vector<unordered_set<int>> components;
  stack<pair<int, int>> st;
  auto last_index = -1;

  auto tarjan = [&](int node, auto &&f) -> void {
    indexes[node] = lowlinks[node] = ++last_index;

    for (auto neigh : graph[node]) {
      if (indexes[neigh] == -1) {
        // Recurse on neigh.
        st.emplace(node, neigh);
        f(neigh, f);

        // Update lowlink.
        lowlinks[node] = min(lowlinks[node], lowlinks[neigh]);

        // Pop component if needed.
        if (lowlinks[neigh] >= indexes[node]) {
          unordered_set<int> comp;
          int child, parent;
          do {
            comp.emplace((parent = st.top().first));
            comp.emplace((child = st.top().second));
            st.pop();
          } while (parent != node || child != neigh);
          components.emplace_back(comp);
        }
      } else {
        lowlinks[node] = min(lowlinks[node], indexes[neigh]);
      }
    }
  };

  for (auto i = 0; i < n; ++i)
    if (indexes[i] == -1) {
      tarjan(i, tarjan);
    }

  fout << components.size() << '\n';
  for (auto &&comp : components) {
    for (auto e : comp) {
      fout << e + 1 << ' ';
    }
    fout << '\n';
  }
}