Cod sursa(job #3226672)

Utilizator andreic06Andrei Calota andreic06 Data 22 aprilie 2024 15:15:36
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>

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

const int V_MAX = 1e5;
const int E_MAX = 2e5;

int V, E;
vector<int> g[1 + V_MAX];
void readInput (void) {
   in >> V >> E;
   for (int i = 1; i <= E; i ++) {
      int a, b; in >> a >> b;
      g[a].push_back (b);
      g[b].push_back (a);
   }
}

struct defNode {
   int depth, low;
   bool visited;
} infos[1 + V_MAX];

stack<int> stk;
int k; vector<int> BCC[1 + V_MAX];

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

   for (int node : g[root]) {
      if (!infos[node].visited) {
        dfs (node, root);
        infos[root].low = min (infos[root].low, infos[node].low);
        if (infos[node].low >= infos[root].depth) {
          k ++;
          while (stk.top () != root) {
             BCC[k].push_back (stk.top ());
             stk.pop ();
          }
          BCC[k].push_back (root);
        }
      }
      else
        infos[root].low = min (infos[root].low, infos[node].depth);
   }
}


int main()
{
  readInput ();
  dfs (1, 0);

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

    return 0;
}