Cod sursa(job #2576719)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 6 martie 2020 22:00:10
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 100000;

vector<int> g[5 + MAX_N];
int st[5 + MAX_N], sz;
int h[5 + MAX_N];
int minBack[5 + MAX_N];
vector<int> bicon[5 + MAX_N];
int bi;

void dfs(int node, int dad) {
  st[++sz] = node;
  for (auto u : g[node]) {
    if (h[u] == 0) {
      int temp;
      temp = sz;
      h[u] = h[node] + 1;
      minBack[u] = h[node] + 1;
      dfs(u, node);
      minBack[node] = min(minBack[node], minBack[u]);
      if (minBack[u] >= h[node]) {
        bicon[++bi].push_back(node);
        while (sz > temp)
          bicon[bi].push_back(st[sz--]);
      }
    } else if (u != dad) {
      minBack[node] = min(minBack[node], h[u]);
    }
  }
}

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);
  }

  h[1] = 1;
  dfs(1, 0);

  printf("%d\n", bi);
  for (int i = 1; i <= bi; i++) {
    for (auto it : bicon[i])
      printf("%d ", it);
    printf("\n");
  }

  return 0;
}