Cod sursa(job #2659040)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 15 octombrie 2020 18:09:08
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <cstdio>
#include <iostream>
#include <vector>
#include <set>

using namespace std;

const int N = 100000 + 7;
int n;
int m;
int d[N];
int mn[N];
bool vis[N];
vector<int> g[N];
vector<int> nodes;
vector<vector<int>> comps;
vector<int> ok[N];
set<pair<int, int>> iz;

void dfs(int a) {
  nodes.push_back(a);
  mn[a] = d[a];
  for (auto &b : g[a]) {
    if (d[b] == -1) {
      d[b] = 1 + d[a];
      dfs(b);
      mn[a] = min(mn[a], mn[b]);
      ok[a].push_back(b);
      continue;
    }
    if (d[b] == d[a] - 1) {
      continue;
    }
    mn[a] = min(mn[a], d[b]);
  }
}

void dfs2(int a) {
  nodes.push_back(a);
  vis[a] = 1;
  for (auto &b : g[a]) {
    if (vis[b] == 0 && !iz.count({a, b})) {
      dfs2(b);
    }
  }
}

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

  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    g[x].push_back(y);
    g[y].push_back(x);
  }
  for (int i = 1; i <= n; i++) {
    d[i] = -1;
  }
  for (int i = 1; i <= n; i++) {
    if (d[i] == -1) {
      nodes.clear();
      d[i] = 0;
      dfs(i);
      for (auto &x : nodes) {
        for (auto &y : ok[x]) {
          if (mn[y] == d[y]) {
            comps.push_back({x, y});
            iz.insert({x, y});
            iz.insert({y, x});
          }
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (vis[i] == 0) {
      nodes.clear();
      dfs2(i);
      if ((int) nodes.size() > 1) {
        comps.push_back(nodes);
      }
    }
  }
  printf("%d\n", (int) comps.size());
  for (auto &vec : comps) {
    for (auto &x : vec) {
      printf("%d ", x);
    }
    printf("\n");
  }
}