Cod sursa(job #2659405)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 16 octombrie 2020 18:59:41
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 100000 + 7;
int n;
int m;
int step;
int d[N];
int dm[N];
int last[N];
vector<int> g[N];
vector<vector<int>> comps;
vector<pair<int, int>> edges;

bool eq(pair<int, int> a, pair<int, int> b) {
  if (a == b) {
    return 1;
  }
  swap(a.first, a.second);
  return (a == b);
}

void dfs(int a, int p, int dep) {
  int kids = 0;
  d[a] = dm[a] = dep;
  for (auto &b : g[a]) {
    if (d[b] == -1) {
      edges.push_back({a, b});
      dfs(b, a, dep + 1);
      dm[a] = min(dm[a], dm[b]);
      kids++;
      if (dep <= dm[b]) {
        comps.push_back({});
        while (1) {
          auto it = edges.back();
          edges.pop_back();
          comps.back().push_back(it.first);
          comps.back().push_back(it.second);
          if (eq(it, {a, b})) {
            break;
          }
        }
      }
      continue;
    }
    if (d[b] >= d[a] - 1) {
      continue;
    }
    edges.push_back({a, b});
    dm[a] = min(dm[a], dm[b]);
  }
}

int main() {
  freopen ("biconex.in", "r", stdin);
  freopen ("biconex.out", "w", stdout);

  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    d[i] = -1;
  }
  for (int i = 1; i <= m; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    g[a].push_back(b);
    g[b].push_back(a);
  }
  for (int i = 1; i <= n; i++) {
    if (d[i] == -1) {
      dfs(i, -1, 0);
    }
  }
  printf("%d\n", (int) comps.size());
  for (auto &vec : comps) {
    sort(vec.begin(), vec.end());
    int y = -1;
    for (auto &x : vec) {
      if (x == y) {
        continue;
      }
      y = x;
      printf("%d ", x);
    }
    printf("\n");
  }
}