Cod sursa(job #2659504)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 16 octombrie 2020 21:34:45
Problema Componente biconexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 100000 + 7;
int n;
int m;
int d[N];
int mn[N];
vector<int> g[N];
vector<pair<int, int>> stk;
vector<vector<int>> comps;

void dfs(int a) {
  mn[a] = d[a];
  for (auto &b : g[a]) {
    if (d[b] == -1) {
      stk.push_back({a, b});
      d[b] = 1 + d[a];
      dfs(b);
      mn[a] = min(mn[a], mn[b]);
      if (d[a] <= mn[b]) {
        vector<int> nodes;
        nodes.push_back(a);
        nodes.push_back(b);
        while (stk.back() != make_pair(a, b)) {
          nodes.push_back(stk.back().first);
          nodes.push_back(stk.back().second);
          stk.pop_back();
        }
        sort(nodes.begin(), nodes.end());
        comps.push_back({nodes[0]});
        for (int i = 1; i < (int) nodes.size(); i++) {
          if (nodes[i - 1] != nodes[i]) {
            comps.back().push_back(nodes[i]);
          }
        }
      }
    } else {
      if (d[b] < d[a] - 1) {
        mn[a] = min(mn[a], d[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 x, y;
    scanf("%d %d", &x, &y);
    g[x].push_back(y);
    g[y].push_back(x);
  }
  for (int i = 1; i <= n; i++) {
    if (d[i] == -1) {
      d[i] = 0;
      dfs(i);
    }
  }
  printf("%d\n", (int) comps.size());
  for (auto &vec : comps) {
    for (auto &x : vec) {
      printf("%d ", x);
    }
    printf("\n");
  }
}