Cod sursa(job #2837080)

Utilizator cadmium_Voicu Mihai-Valeriu cadmium_ Data 21 ianuarie 2022 18:09:35
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <bits/stdc++.h>

using namespace std;

#define cin fin
#define cout fout
ifstream cin("biconex.in");
ofstream cout("biconex.out");
#define stack incaasteptgluma8
const int nmax = 1e5 + 5;
const int mmax = 2e5 + 5;

int n, m;

struct edg {
  int u, v, other;
  bool operator !=(const edg& a) const {
    return pair<int,int>{u,v} != pair<int,int>{a.u,a.v};
  }
} edge[mmax];

vector< vector<int> > bicon;

vector<int> stack;

vector<int> graph[nmax];

int occ[nmax];

static void redux(edg left) {
  bicon.push_back(vector<int>());
  while(stack.size() && edge[stack.back()] != left) {
    bicon.back().push_back(edge[stack.back()].u);
    bicon.back().push_back(edge[stack.back()].v);
    stack.pop_back();
  }
  bicon.back().push_back(edge[stack.back()].u);
  bicon.back().push_back(edge[stack.back()].v);
  stack.pop_back();
  return;
}

int depth[nmax];
int maxdepth[nmax];

static void dfs(int node, int f) {
  int c;
  depth[node] = depth[f] + 1;
  maxdepth[node] = depth[node];
  occ[node] = 1;
  for(auto x : graph[node]) {
    c = edge[x].other ^ node;
    if(c == f)
      continue;
    if(!occ[c]) {
      stack.push_back(x);
      dfs(c, node);
      maxdepth[node] = min(maxdepth[node], maxdepth[c]);
      if(maxdepth[c] >= depth[node]) {
        redux(edge[x]);
      }
    }
    else
      maxdepth[node] = min(maxdepth[node], depth[c]);
  }
  return;
}

int main() {
  cin >> n >> m;
  for(int i = 0, x, y; i < m; i++) {
    cin >> x >> y;
    --x;
    --y;
    if(x > y)
      swap(x, y);
    edge[i] = edg{x, y, x ^ y};
    graph[x].push_back(i);
    graph[y].push_back(i);
  }
  dfs(0,0);
  cout << bicon.size() << '\n';
  for(auto x :bicon) {
    sort(x.begin(), x.end());
    x.resize(distance(x.begin(),unique(x.begin(), x.end())));
    for(auto y : x)
      cout << y + 1 << ' ';
    cout << '\n';
  }
}