Cod sursa(job #3293762)

Utilizator andreic06Andrei Calota andreic06 Data 12 aprilie 2025 15:42:09
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>

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

const int N_MAX = 1e5;

int N, M; vector<int> g[1 + N_MAX];
struct defNode {
    int depth;
    int low;
} infos[1 + N_MAX];

stack<int> S; bool visited[1 + N_MAX];
int k = 0; vector<int> BCC[1 + N_MAX];
void get_bcc (int root, int node) {
   k ++;
   while (S.top () != node) {
      BCC[k].push_back (S.top ());
      S.pop ();
   }
   BCC[k].push_back (node); S.pop ();
   BCC[k].push_back (root);
}

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

   int children = 0;
   for (int node : g[root]) {
      if (node == p) continue;
      if (visited[node]) infos[root].low = min (infos[root].low, infos[node].depth); /// back-edge
      else {
        children ++;
        dfs (node, root);
        infos[root].low = min (infos[root].low, infos[node].low);
        if (infos[node].low >= infos[root].depth) /// root = art point
          get_bcc (root, node);
      }
   }
}
int main()
{
   fin >> N >> M;
   for (int i = 1; i <= M; i ++) {
      int u, v; fin >> u >> v;
      g[u].push_back (v);
      g[v].push_back (u);
   }

   dfs (1, 0);

   fout << k << "\n";
   for (int i = 1; i <= k; i ++) {
       sort (BCC[i].begin (), BCC[i].end ());
       for (int x : BCC[i]) fout << x << " ";
       fout << "\n";
   }

    return 0;
}