Cod sursa(job #2817046)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 12 decembrie 2021 18:55:13
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb
#include <iostream>
#include <fstream>
#include <vector>

#define d(a) std::cout << a << std::endl;

const int INF = 1e9 + 7;
const int NMAX = 1e5;

int n, m;

std::vector<int> graph[1 + NMAX];

std::vector<std::pair<int, int>> stack;

int height[1 + NMAX];

std::vector<std::vector<int>> ans;

int dfs(int node, int h) {
  //std::printf("called for node = %d\n", node);
  height[node] = h;

  int minHeight = INF;

  for (int child : graph[node]) {
    if (height[child] != 0)
      minHeight = std::min(minHeight, height[child]);
    else {
      //std::printf("node %d -> child %d\n", node, child);
      stack.emplace_back(node, child);
      int childMinHeight = dfs(child, 1 + h);

      if (childMinHeight >= h) {
        //std::printf("found component @ node = %d, child = %d w/ height = %d\n", node, child, childMinHeight);
        ans.emplace_back();

        while (stack.back().first != node && stack.back().second != child) {
          ans.back().push_back(stack.back().second);
          stack.pop_back();
        }

        ans.back().push_back(child);
        ans.back().push_back(node);
        stack.pop_back();
      }

      minHeight = std::min(minHeight, childMinHeight);
    }
  }

  return minHeight;
}

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

  in >> n >> m;

  while (m--) {
    int a, b;
    in >> a >> b;

    // std::cout << a << " -- " << b << "\n";

    graph[a].push_back(b);
    graph[b].push_back(a);
  }

  dfs(1, 1);

  out << ans.size() << '\n';

  for (auto &comp : ans) {
    for (int i : comp)
      out << i << ' ';
    out << '\n';
  }

  return 0;
}