Cod sursa(job #1782741)

Utilizator cella.florescuCella Florescu cella.florescu Data 18 octombrie 2016 15:40:31
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100000;

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

struct StackNode {
  int nod, son;
} x;

stack <StackNode> st;

inline int minim(int a, int b) {
  if (a < b)
    return a;
  return b;
}

inline void add_comp(int node) {
  vector <int> comp;
  do {
    x = st.top();
    comp.push_back(x.son);
    st.pop();
  } while (x.nod != node);
  comp.push_back(node);
  ans.push_back(comp);
}

void dfs(int node, int parent) {
  lev[node] = low[node] = lev[parent] + 1;
  for (auto i : g[node])
    if (i != parent)
      if (lev[i])
        low[node] = minim(low[node], lev[i]);
      else {
        st.push({node, i});
        dfs(i, node);
        low[node] = minim(low[node], low[i]);
        if (low[i] >= lev[node])
          add_comp(node);
      }
}

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