Cod sursa(job #2940095)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 14 noiembrie 2022 20:34:36
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 100000 + 7;
int n;
int m;
vector<int> g[N];
int dep[N];
int mindep[N];
vector<vector<int>> all;
vector<pair<int, int>> stk;

void dfs(int a) {
  mindep[a] = dep[a];

  for (auto &b : g[a]) {
    if (dep[b] == -1) {
      dep[b] = 1 + dep[a];
      stk.push_back({a, b});
      dfs(b);
      mindep[a] = min(mindep[a], mindep[b]);
      if (mindep[b] >= dep[a]) {

        vector<int> cur;
        while (1) {
          assert(!stk.empty());
          auto it = stk.back();
          cur.push_back(it.first);
          cur.push_back(it.second);
          stk.pop_back();
          if (it == make_pair(a, b)) {
            break;
          }
        }
        sort(cur.begin(), cur.end());
        cur.resize(unique(cur.begin(), cur.end()) - cur.begin());
        all.push_back(cur);
      }
    } else {
      if (dep[b] < dep[a] - 1) {
        mindep[a] = min(mindep[a], dep[b]);
      }
    }
  }
}

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

  ///freopen ("input.txt", "r", stdin);

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

  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  for (int i = 1; i <= n; i++) {
    dep[i] = -1;
  }
  for (int i = 1; i <= n; i++) {
    if (dep[i] == -1) {
      dep[i] = 0;
      dfs(i);
      assert(stk.empty());
    }
  }


  cout << (int) all.size() << "\n";
  for (auto &v : all) {
    for (auto &x : v) {
      cout << x << " ";
    }
    cout << "\n";
  }
  return 0;
}