Cod sursa(job #2956836)

Utilizator andreic06Andrei Calota andreic06 Data 20 decembrie 2022 19:50:20
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>

using namespace std;
const int VMAX = 1e5;
const int EMAX = 1e5;
const int RAND_ROOT = 1, AUX_PARENT = 0;

int depth[1 + VMAX], low[1 + VMAX];
bool visited[1 + VMAX]; vector<int> g[1 + VMAX];

int counter = 0;
vector<int> bc[1 + VMAX];
stack<int> bcStack;

void dfs (int root, int p) {
    visited[root] = true;
    depth[root] = depth[p] + 1;
    low[root] = depth[root];
    bcStack.push (root);

    for (int node : g[root]) {
       if (node != p) {
         if (visited[node])  /// back edge
           low[root] = min(low[root], depth[node]);
         else {
           dfs (node, root);
           low[root] = min (low[root], low[node]);
           if (low[node] >= depth[root]) {
             while (bcStack.top () != root) {
                bc[counter].push_back (bcStack.top ());
                bcStack.pop ();
             }
             bc[counter].push_back (root);
             counter ++;
           }
         }
       }
    }
}


int main()
{
   ifstream in ("biconex.in");
   ofstream out ("biconex.out");

   int V, E; in >> V >> E;
   for (int i = 1; i <= E; i ++) {
      int u, v; in >> u >> v;
      g[u].push_back (v);
      g[v].push_back (u);
   }
   dfs (RAND_ROOT, AUX_PARENT);


   out << counter << "\n";
   for (int idx = 0; idx < counter; idx ++) {
      for (int node : bc[idx])
         out << node << " ";
      out << "\n";
   }
    return 0;
}