Cod sursa(job #2790285)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 28 octombrie 2021 18:45:47
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>

using namespace std;

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

const int maxN = (int)1e5;

int n, m;

vector<int> g[maxN];

bool visited[maxN];

int l[maxN], d[maxN];

vector<pair<int, int>> edges;

vector<vector<int>> result;

void addBiconnected(int x, int y) {
  vector<int> comp;
  while ((int)edges.size() > 0 && edges.back() != make_pair(x, y)) {
    comp.push_back(edges.back().first);
    comp.push_back(edges.back().second);
    edges.pop_back();
  }
  comp.push_back(edges.back().first);
  comp.push_back(edges.back().second);
  edges.pop_back();
  result.push_back(comp);
}

void dfs(int u, int cnt) {
  visited[u] = true;
  l[u] = d[u] = cnt;
  cnt++;
  for (int v : g[u]) {
    if (!visited[v]) {
      edges.emplace_back(u, v);
      dfs(v, cnt);
      l[u] = min(l[u], l[v]);
      if (d[u] <= l[v]) {
        addBiconnected(u, v);
      }
    } else {
      l[u] = min(l[u], d[v]);
    }
  }
}

int main() {
  in >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    in >> u >> v;
    u--; v--;
    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)result.size() << "\n";
  for (vector<int> &comp : result) {
    sort(comp.begin(), comp.end());
    int lst = -1;
    for (int u : comp) {
      if (u != lst) {
        out << u + 1 << " ";
      }
      lst = u;
    }
    out << "\n";
  }
  return 0;
}