Cod sursa(job #2669142)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 6 noiembrie 2020 10:58:24
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> g;

vector<vector<int>> ans;

vector<bool> visited;

vector<int> reach;

vector<int> id;

stack<pair<int, int>> st;

void solver(int u, int v) {
  ans.push_back(vector<int>{});
  int comp_numer = (int)ans.size() - 1;
  while (true) {
    int x = st.top().first, y = st.top().second;
    st.pop();
    ans[comp_numer].push_back(x);
    ans[comp_numer].push_back(y);
    if (x == u && y == v) {
      return;
    }
  }
}

void dfs(int u, int cnt) {
  id[u] = reach[u] = cnt;
  cnt += 1;
  visited[u] = true;
  for (int v : g[u]) {
    if (!visited[v]) {
      st.push(make_pair(u, v));
      dfs(v, cnt);
      reach[u] = min(reach[u], reach[v]);
      if (reach[v] >= id[u]) {
        solver(u, v);
      }
    } else {
      reach[u] = min(reach[u], id[v]);
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  ifstream in("biconex.in"); ofstream out("biconex.out");
  int n, m; in >> n >> m;
  g.resize(n);
  visited.resize(n, false);
  reach.resize(n);
  id.resize(n);
  for (int i = 0; i < m; ++i) {
    int u, v; in >> u >> v;
    u -= 1;
    v -= 1;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  int cnt = 0;
  for (int i = 0; i < n; ++i) {
    if (!visited[i]) {
      dfs(i, cnt);
    }
  }
  out << (int)ans.size() << "\n";
  for (int i = 0; i < (int)ans.size(); ++i) {
    sort(ans[i].begin(), ans[i].end());
    ans[i].erase(unique(ans[i].begin(), ans[i].end()), ans[i].end());
    for (int value : ans[i]) {
      out << 1 + value << " ";
    }
    out << "\n";
  }
  return 0;
}