Cod sursa(job #2487472)

Utilizator vladisimovlad coneschi vladisimo Data 4 noiembrie 2019 20:15:52
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <algorithm>
#include <cstdio>
#include <stack>
#include <vector>

const int MAX_N = 1e5;

std::vector<int> G[2 + MAX_N];
std::vector<std::vector<int>> sol;

std::stack<std::pair<int, int>> edges;

int count = 0, level[2 + MAX_N], up[2 + MAX_N];

bool visited[2 + MAX_N];

void print(int u, int v) {
  int x, y;
  std::vector<int> comp;
  do {
    x = (edges.top()).first;
    y = (edges.top()).second;
    comp.push_back(x);
    comp.push_back(y);
    edges.pop();
  } while (x != u || y != v);
  sol.push_back(comp);
}

void dfs(int u, int parent, int lev) {
  visited[u] = true;
  up[u] = level[u] = lev;
  for (int v : G[u]) {
    if (!visited[v] && v != parent) {
      edges.push({v, u});
      dfs(v, u, lev + 1);
      up[u] = std::min(up[u], up[v]);
      if (up[v] >= level[u])
        print(v, u);
    } else if (v != parent && visited[v])
        up[u] = std::min(up[u], level[v]);
  }
}

int main() {
  freopen("biconex.in", "r", stdin);
  freopen("biconex.out", "w", stdout);
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    G[u].push_back(v);
    G[v].push_back(u);
  }
  dfs(1, 0, 0);
  printf("%d\n", sol.size());
  for (auto comp : sol) {
    std::sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    for (auto u : comp)
      printf("%d ", u);
    printf("\n");
  }
  return 0;
}