Cod sursa(job #2224375)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 23 iulie 2018 20:59:39
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>

using namespace std;

struct Edge {
  int a, b;
  int other(int node) {
    return a ^ b ^ node;
  }
}e[200005];

vector<int>G[100005];
vector<vector<int> >ans;
int stk[200005];
int h[100005], low[100005];
bool v1[100005], viz[100005];
int top;

void dfs(int nod, int f) {
  viz[nod] = 1;
  for (auto it:G[nod]) {
    int v = e[it].other(nod);
    if (!viz[v]) {
      stk[++top] = it;
      low[v] = h[v] = h[nod] + 1;
      dfs(v, it);
      low[nod] = min(low[nod], low[v]);
      if (low[v] >= h[nod]) {
        vector<int>bic;
        do {
          int a = e[stk[top]].a;
          int b = e[stk[top]].b;
          top--;
          if (!v1[a])
            bic.push_back(a), v1[a] = 1;
          if (!v1[b])
            bic.push_back(b), v1[b] = 1;
        } while(stk[top + 1] != it);
        for (auto it:bic)
          v1[it] = 0;
        ans.push_back(bic);
      }
    } else if (it != f) {
      low[nod] = min(low[nod], h[v]);
    }
  }
}

int main() {
  ifstream cin("biconex.in");
  ofstream cout("biconex.out");

  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int x, y;
    cin >> x >> y;
    e[i] = {x, y};
    G[x].push_back(i);
    G[y].push_back(i);
  }

  dfs(1, 0);

  cout << ans.size() << '\n';
  for (auto it:ans) {
    for (auto x:it)
      cout << x << ' ';
    cout << '\n';
  }
  return 0;
}