Cod sursa(job #2487187)

Utilizator vladisimovlad coneschi vladisimo Data 4 noiembrie 2019 10:31:34
Problema Componente biconexe Scor 56
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <cstdio>
#include <set>
#include <stack>
#include <vector>

const int MAX_N = 1e5;

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

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

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;
  count++;
  do {
    x = (edges.top()).first;
    y = (edges.top()).second;
    sol[count].insert(x);
    sol[count].insert(y);
    edges.pop();
  } while ((x != u || y != v) && (x != v && y != u));
}

void dfs(int u, int parent) {
  visited[u] = true;
  up[u] = level[u];
  for (int v : G[u]) {
    if (v != parent && level[u] > level[v])
      edges.push({v, u});
    if (!visited[v]) {
      level[v] = level[u] + 1;
      dfs(v, u);
      up[u] = std::min(up[u], up[v]);
      if (up[v] >= level[u])
        print(u, v);
    } else
      if (v != parent)
        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);
  }
  for (int i = 1; i <= n; i++)
    if (!visited[i]) {
      level[i] = 1;
      dfs(i, -1);
    }
  printf("%d\n", count);
  for (int i = 1; i <= count; i++) {
    for (int j : sol[i])
      printf("%d ", j);
    printf("\n");
  }
  return 0;
}