Cod sursa(job #2777805)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 24 septembrie 2021 20:04:01
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <bits/stdc++.h>

using namespace std;

const int N = (int) 1e5 + 7;
int n, m, q, depInitial[N], minDepInitial[N];
vector<int> gInitial[N], kidsInitial[N], g[N];
vector<pair<int, int>> stk;
vector<vector<int>> comps;

void dfsInitial(int a) {
  minDepInitial[a] = depInitial[a];

  for (auto &b : gInitial[a]) {
    if (depInitial[b] == 0) {
      stk.push_back({a, b});
      kidsInitial[a].push_back(b);
      depInitial[b] = 1 + depInitial[a];
      dfsInitial(b);
      minDepInitial[a] = min(minDepInitial[a], minDepInitial[b]);
      if (depInitial[a] <= minDepInitial[b]) {
        vector<int> sol;
        while (1) {
          auto it = stk.back();
          sol.push_back(it.first);
          sol.push_back(it.second);
          stk.pop_back();
          if (it == make_pair(a, b)) break;
        }
        sort(sol.begin(), sol.end());
        comps.push_back({});
        for (int i = 0; i < (int) sol.size(); i++) {
          if (i == 0 || (sol[i] != sol[i - 1])) {
            comps.back().push_back(sol[i]);
          }
        }
      }
    } else {
      if (depInitial[b] < depInitial[a] - 1) {
        minDepInitial[a] = min(minDepInitial[a], depInitial[b]);
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);

  freopen ("biconex.in", "r", stdin);
  freopen ("biconex.out", "r", stdin);

  cin >> n >> m;

  for (int i = 1; i <= m; i++) {
    int foo, bar;
    cin >> foo >> bar;
    gInitial[foo].push_back(bar);
    swap(foo, bar);
    gInitial[foo].push_back(bar);
  }

  depInitial[1] = 1;
  dfsInitial(1);

  cout << (int) comps.size() << "\n";
  for (auto &c : comps) {
    for (auto &x : c) {
      cout << x << " ";
    }
    cout << "\n";
  }


  return 0;
}