Cod sursa(job #3197098)

Utilizator Luca_Miscocilucainfoarena Luca_Miscoci Data 25 ianuarie 2024 17:21:06
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <vector>
#include <stack>
#include <string.h>

using namespace std;

const int nmax = 1e5 + 4;

stack <int> st;
vector <int> graf[nmax + 1];
vector <vector<int>> comp;
int depth[nmax + 1];
int lowpoint[nmax + 1];
bool aux[nmax + 1];

void dfs (int node, int parent, int low){

  depth[node] = low;
  lowpoint[node] = low;
  st.push(node);

  for (auto neighbour : graf[node]){
    if (neighbour == parent)
      continue;

    if (depth[neighbour] == 0){

      dfs (neighbour, node, low + 1);

      if (lowpoint[neighbour] >= depth[node]){

        vector <int> sol;
        while (!st.empty() && st.top() != neighbour){
          sol.push_back (st.top());
          st.pop();
        }
        st.pop();

        sol.push_back(node);
        sol.push_back(neighbour);
        comp.push_back(sol);
      }

      lowpoint[node] = min (lowpoint[node] , lowpoint[neighbour]);
    }

    else{
      lowpoint[node] = min (lowpoint[node], depth[neighbour]);
    }
  }
}

int main(){

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

  int n, m;
  fin >> n >> m;

  for (int i = 0; i < m; i++){
    int x, y;
    fin >> x >> y;

    graf[x].push_back(y);
    graf[y].push_back(x);
  }

  for (int i = 1; i <= n; i++)
    if (depth[i] == 0)
      dfs (i, i, 1);

  fout << comp.size() << "\n";
  for (auto solution: comp){
    for (auto nod: solution)
      fout << nod << " ";
    fout << "\n";
  }
  return 0;
}