Cod sursa(job #2122668)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 5 februarie 2018 13:20:32
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int NMAX = 100005;

vector<int> g[NMAX];
stack<int> st;
int n, m, index[NMAX], lowlink[NMAX], globalIndex = -1;
vector<vector<int>> c;

void component(int node, int parent) {
  vector<int> comp;
  comp.push_back(parent);
  while (st.top() != node) {
    comp.push_back(st.top());
    st.pop();
  }
  comp.push_back(node);
  st.pop();
  c.push_back(comp);
}

void dfs(int node, int parent) {
  index[node] = lowlink[node] = ++globalIndex;
  for (int next : g[node]) {
    if (next == parent)
      continue;
    if (index[next])
      lowlink[node] = min(lowlink[node], index[next]);
    else {
      st.push(next);
      dfs(next, node);
      lowlink[node] = min(lowlink[node], lowlink[next]);
      if (lowlink[next] >= index[node])
        component(next, node);
    }
  }
}

void read() {
  in >> n >> m;
  while (m--) {
    int x, y;
    in >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
}

int main() {
  read();
  for (int i = 1; i <= n; i++) {
    st.push(i);
    if (!index[i])
      dfs(i, 0);
    st.pop();
  }

  out << c.size() << '\n';
  for (auto comp : c) {
    for (int item : comp)
      out << item << ' ';
    out << '\n';
  }

  return 0;
}