Cod sursa(job #2218281)

Utilizator cella.florescuCella Florescu cella.florescu Data 4 iulie 2018 05:45:29
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;

vector < int > g[MAXN + 1], stk;
vector < vector < int > > bcc;
int lev[MAXN + 1], low[MAXN + 1];

inline void add_bcc(int node, int son) {
  vector < int > comp;
  do {
    comp.push_back(stk.back());
    stk.pop_back();
  } while (comp.back() ^ son);
  comp.push_back(node);
  bcc.push_back(comp);
}

void dfs(int node, int father) {
  low[node] = lev[node] = lev[father] + 1;
  stk.push_back(node);
  for (auto it : g[node])
    if (it ^ father) {
      if (lev[it]) {
        low[node] = min(lev[it], low[node]);
      } else {
        dfs(it, node);
        low[node] = min(low[node], low[it]);
        if (low[it] >= lev[node])
          add_bcc(node, it);
      }
    }
}

int main()
{
    int n, m;
    ifstream fin("biconex.in");
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
      int x, y;
      fin >> x >> y;
      g[x].push_back(y);
      g[y].push_back(x);
    }
    fin.close();
    dfs(1, 0);
    ofstream fout("biconex.out");
    fout << bcc.size() << '\n';
    for (auto comp : bcc) {
      for (auto it : comp)
        fout << it << " ";
      fout << '\n';
    }
    fout.close();
    return 0;
}