Cod sursa(job #1952795)

Utilizator oanaroscaOana Rosca oanarosca Data 4 aprilie 2017 13:13:07
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

int n, m, x, y, nrc, low[100001], niv[100001];
bool viz[100001];
vector<int> v[100001], comp[100001];
stack<int>st;

void dfs (int nod) {
  vector<int>::iterator i;

  viz[nod] = 1; low[nod] = niv[nod];
  st.push(nod);
  for (i = v[nod].begin(); i != v[nod].end(); i++)
    if (viz[*i])
      low[nod] = min(low[nod], niv[*i]);
    else {
      niv[*i] = niv[nod]+1;
      dfs(*i);
      low[nod] = min(low[nod], low[*i]);
      if (low[*i] >= niv[nod]) {
        nrc++;
        while (st.top() != (*i))
          comp[nrc].push_back(st.top()), st.pop();
        comp[nrc].push_back(st.top()), st.pop();
        comp[nrc].push_back(nod);
      }
    }
}

int main () {
  ifstream fi("biconex.in");
  ofstream fo("biconex.out");
  fi >> n >> m;
  for (int i = 1; i <= m; i++)
    fi >> x >> y, v[x].push_back(y), v[y].push_back(x);
  for (int i = 1; i <= n; i++)
    if (!viz[i])
      dfs(i);
  fo << nrc << '\n';
  for (int i = 1; i <= nrc; i++) {
    vector<int>::iterator j;
    for (j = comp[i].begin(); j != comp[i].end(); j++)
      fo << (*j) << ' ';
    fo << '\n';
  }
  return 0;
}