Cod sursa(job #3372183)

Utilizator RaducuSebasRaducu Sebastian RaducuSebas Data 2 noiembrie 2026 18:01:13
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fi("biconex.in");
ofstream fo("biconex.out");

int n, m, timp;
vector<int> ad[100005];
int lvl[100005], low[100005];
vector<pair<int, int>> st;
vector<vector<int>> sol;

void dfs(int nod, int tata) {
  lvl[nod] = low[nod] = ++timp;

  for (int vecin : ad[nod]) {
    if (vecin == tata)
      continue;
    if (lvl[vecin]) {
      low[nod] = min(low[nod], lvl[vecin]);
      if (lvl[vecin] < lvl[nod])
        st.push_back({nod, vecin});
    } else {
      st.push_back({nod, vecin});
      dfs(vecin, nod);
      low[nod] = min(low[nod], low[vecin]);
      if (low[vecin] >= lvl[nod]) {
        vector<int> comp;
        while (true) {
          auto much = st.back();
          st.pop_back();
          comp.push_back(much.first);
          comp.push_back(much.second);
          if (much.first == nod && much.second == vecin)
            break;
        }
        sort(comp.begin(), comp.end());
        comp.erase(unique(comp.begin(), comp.end()), comp.end());
        sol.push_back(comp);
      }
    }
  }
}

int main() {
  fi >> n >> m;
  int x, y;
  for (int i = 1; i <= m; i++) {
    fi >> x >> y;
    ad[x].push_back(y);
    ad[y].push_back(x);
  }

  for (int i = 1; i <= n; i++)
    if (!lvl[i])
      dfs(i, 0);

  fo << sol.size() << "\n";
  for (auto &comp : sol) {
    for (int nod : comp)
      fo << nod << " ";
    fo << "\n";
  }

  return 0;
}