Cod sursa(job #1758038)

Utilizator crushackPopescu Silviu crushack Data 16 septembrie 2016 12:48:59
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <algorithm>
#include <fstream>
#include <functional>
#include <stack>
#include <vector>

using namespace std;

vector<vector<int>> biconex(vector<vector<int>>& graph) {
  vector<vector<int>> ans;
  vector<int> idx(graph.size(), -1);
  vector<int> low(graph.size());
  stack<pair<int, int>> st;
  int index = 0;

  function<vector<int>(pair<int, int>)>
  make_component = [&](pair<int, int> edge) -> vector<int> {
    vector<int> ans;
    pair<int, int> current;
    do {
        current = st.top();
        st.pop();
        ans.push_back(current.first);
        ans.push_back(current.second);
    } while (edge != current);
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    return ans;
  };

  function<void(int, int)>
  dfs = [&](int node, int parent) {
    idx[node] = low[node] = index ++;

    for (int adj : graph[node]) {
      if (adj == parent) continue;
      if (idx[adj] == -1) {
        st.push({node, adj});
        dfs(adj, node);
        low[node] = min(low[node], low[adj]);
        if (low[adj] >= idx[node])
          ans.push_back(make_component({node, adj}));
      } else {
        low[node] = min(low[node], idx[adj]);
      }
    }

    -- index;
  };

  dfs(1, 0);
  return ans;
}

int main() {
  ifstream fin("biconex.in");
  ofstream fout("biconex.out");
  vector<vector<int>> graph;
  int n, m;

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

  auto ans = biconex(graph);

  fout << ans.size() << "\n";
  for (auto comp : ans) {
    for (int element : comp) {
      fout << element << " ";
    }
    fout << "\n";
  }

  return 0;
}