Cod sursa(job #2186289)

Utilizator cella.florescuCella Florescu cella.florescu Data 25 martie 2018 14:31:56
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;

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

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

void bicon_dfs(int node, int father) {
  low[node] = level[node] = level[father] + 1;
  stk.push_back(node);
  for (auto it : g[node])
    if (it ^ father)
      if (level[it])
        low[node] = min(low[node], level[it]);
      else {
        bicon_dfs(it, node);
        low[node] = min(low[node], low[it]);
        if (level[node] <= low[it])
          add_comp(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();
    bicon_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;
}