Cod sursa(job #2574069)

Utilizator popashtefan10Popa Stefan popashtefan10 Data 5 martie 2020 20:12:17
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define NMAX 100000

using namespace std;

struct muchie {
  int t, f;

  muchie(int tt = 0, int ff = 0) {
    t = tt;
    f = ff;
  }
};

int n, m, ncomp, num, start;
int dfn[NMAX + 5], low[NMAX + 5];
vector<muchie> st;
vector<int> v[NMAX + 5], cbc[NMAX + 5];

void comp_biconexa(int u, int x) {
  muchie crt;

  ncomp++;
  do {
    crt = st.back();
    st.pop_back();

    cbc[ncomp].push_back(crt.t);
    cbc[ncomp].push_back(crt.f);
  } while(crt.t != u || crt.f != x);

  sort(cbc[ncomp].begin(), cbc[ncomp].end());
}

void biconex(int u, int tu) {
  dfn[u] = low[u] = ++num;
  for(int x: v[u]) {
    if(x == tu)
      continue;

    if(dfn[x] < dfn[u])
      st.push_back(muchie(u, x));

    if(dfn[x] == -1) { /// nu e muchie de intoarcere
      biconex(x, u);
      low[u] = min(low[u], low[x]);
      if(low[x] >= dfn[u]) /// u e pct de articulatie
        comp_biconexa(u, x);
    }
    else
      low[u] = min(low[u], dfn[x]);
  }
}

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

  scanf("%d %d", &n, &m);
  for(int i = 1; i <= n; i++)
    dfn[i] = low[i] = -1;
  for(int i = 1; i <= m; i++) {
    scanf("%d %d", &x, &y);
    v[x].push_back(y);
    v[y].push_back(x);
  }

  ncomp = num = 0;
  start = 1;
  st.push_back(muchie(-1, 1));
  biconex(1, -1);

  printf("%d\n", ncomp);
  for(int i = 1; i <= ncomp; i++) {
    for(int j = 0; j < cbc[i].size(); j++)
      if(j == 0 || cbc[i][j] != cbc[i][j - 1])
        printf("%d ", cbc[i][j]);
    printf("\n");
  }

  return 0;
}