Cod sursa(job #2530855)

Utilizator lucametehauDart Monkey lucametehau Data 25 ianuarie 2020 13:10:31
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream cin ("biconex.in");
ofstream cout ("biconex.out");

int n, m, x, y;

vector <int> g[100005], comp;
vector <vector <int>> bicomp;
vector <pair <int, int>> edges;
int disc[100005], low[100005];

void dfs(int nod, int tata, int nr) {
  disc[nod] = low[nod] = nr;
  for(auto &fiu : g[nod]) {
    if(fiu == tata)
      continue;
    if(!disc[fiu]) {
      edges.push_back({nod, fiu});
      dfs(fiu, nod, nr + 1);
      low[nod] = min(low[nod], low[fiu]);
      if(low[fiu] >= disc[nod]) {
        comp.clear();
        do {
          x = edges.back().first, y = edges.back().second;
          comp.push_back(x); comp.push_back(y);
          edges.pop_back();
        } while(x != nod || y != fiu);
        sort(comp.begin(), comp.end());
        auto it = unique(comp.begin(), comp.end());
        comp.resize(it - comp.begin());
        bicomp.push_back(comp);
      }
    } else
      low[nod] = min(low[nod], disc[fiu]);
  }
}

int main() {
  cin >> n >> m;
  for(; m; m--) {
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  dfs(1, 0, 1);
  cout << bicomp.size() << "\n";
  for(auto &i : bicomp) {
    for(auto &j : i)
      cout << j << " ";
    cout << "\n";
  }
  return 0;
}