Cod sursa(job #2188863)

Utilizator NeredesinI am not real Neredesin Data 27 martie 2018 15:32:22
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>

using namespace std;

ifstream in ("biconex.in");
ofstream out ("biconex.out");

const int NMAX = 1e5 + 5;


int m, n, k, nv;
int niv[NMAX], l[NMAX];

vector < int > g[NMAX];
stack < pair < int, int > > s;
set < int > comp[NMAX];


void get_data(int x, int y) {
  int xs, ys;
  do {
    xs = s.top().first;
    ys = s.top().second;

    comp[k].insert (xs);
    comp[k].insert (ys);
    s.pop();
  } while (xs != x || ys != y);
}

void dfs(int x, int par) {
  l[x] = niv[x] = ++nv;
  for (const int &y : g[x]) {
    if (y == par)
      continue;
    if (!niv[y]) {
      s.push ({x, y});
      dfs (y, x);
      l[x] = min(l[x], l[y]);
      if (l[y] >= niv[x]) {
        k++;
        get_data(x, y);
      }
    } else
      l[x] = min(l[x], niv[y]);
  }
}

int main()
{
  in >> n >> m;
  for (int i = 0; i < m; ++i) {
    int x, y;
    in >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  dfs (1, 0);
  out << k << '\n';
  for (int i = 1; i <= k; ++i) {
    for (const int &node : comp[i])
      out << node << ' ';
    out << '\n';
  }

  in.close();
  out.close();
  return 0;
}