Cod sursa(job #2981748)

Utilizator raresgherasaRares Gherasa raresgherasa Data 18 februarie 2023 17:03:55
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <bits/stdc++.h>

using namespace std;

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

const int kN = 1e5 + 5;

vector<vector<int>>biconex;
vector<pair<int, int>>critics;
vector<int>g[kN];
int n, m, t;
int low[kN], tin[kN], stk[kN];
bool visited[kN], art[kN];

vector<int>add (int x, int y){
   vector<int>ans;
   while (stk[stk[0]] != y){
      ans.push_back(stk[stk[0]]);
      --stk[0];
   }
   ans.push_back(x);
   ans.push_back(y);
   --stk[0];
   return ans;
}

void dfs (int nod, int dad = -1){
   stk[++stk[0]] = nod;
   visited[nod] = true;
   tin[nod] = low[nod] = ++t;
   int children = 0;
   for (int u : g[nod]){
      if (u == dad){
         continue;
      }
      if (visited[u]){
         low[nod] = min(low[nod], tin[u]);
      }
      else{
         dfs(u, nod);
         low[nod] = min(low[nod], low[u]);
         if (low[u] > tin[nod]){
            critics.push_back(make_pair(nod, u));
         }
         if (low[u] >= tin[nod] && dad != -1){
            art[nod] = true;
         }
         if (low[u] >= tin[nod]){
            biconex.push_back(add(nod, u));
         }
         ++children;
      }
   }
   if (dad == -1 && children > 1){
      art[nod] = true;
   }
}

int main(){
   ios_base::sync_with_stdio(false);

   fin >> n >> m;
   for (int i = 1; i <= m; i++){
      int x, y; fin >> x >> y;
      g[x].push_back(y);
      g[y].push_back(x);
   }
   for (int i = 1; i <= n; i++){
      if (!visited[i]){
         dfs(i);
      }
   }
   fout << (int)biconex.size() << '\n';
   for (auto y : biconex){
      sort(y.begin(), y.end());
      for (int x : y){
         fout << x << " ";
      }
      fout << '\n';
   }
}