Cod sursa(job #2575441)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 6 martie 2020 13:32:28
Problema Componente biconexe Scor 100
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100005;
const int MAXM = 200005;

struct Edge {
  int u, v;
  int other (const int node) {
    return u ^ v ^ node;
  }
}e[MAXM];

vector<int>G[MAXN];
vector<vector<int> >bic;

bool vis[MAXN], viz[MAXN];
int h[MAXN], low[MAXN];
int stk[MAXM], top;

void dfs(int node, int papa) {
  vis[node] = 1;
  for (auto it:G[node]) {
    int u = e[it].other(node);
    if (!vis[u]) {
      stk[++top] = it;
      h[u] = low[u] = h[node] + 1;
      dfs(u, it);
      low[node] = min(low[node], low[u]);
      if (low[u] >= h[node]) {
        vector<int>b;
        do {
          int x = e[stk[top]].u;
          int y = e[stk[top]].v;
          top--;
          if (!viz[x])
            viz[x] = 1, b.push_back(x);
          if (!viz[y])
            viz[y] = 1, b.push_back(y);
        } while (stk[top + 1] != it);
        for (auto it:b)
          viz[it] = 0;
        bic.push_back(b);
      }
    } else if (it != papa) {
      low[node] = min(low[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) {
    scanf("%d%d", &e[i].u, &e[i].v);
    G[e[i].u].push_back(i);
    G[e[i].v].push_back(i);
  }

  dfs(1, 0);

  printf("%d\n", bic.size());
  for (auto b:bic) {
    for (auto it:b)
      printf("%d ", it);
    printf("\n");
  }

  return 0;
}