Cod sursa(job #2197801)

Utilizator georgeromanGeorge Roman georgeroman Data 22 aprilie 2018 21:44:43
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.15 kb
#include <algorithm>
#include <fstream>
#include <stack>
#include <utility>
#include <vector>

void bcGet(std::stack<std::pair<unsigned, unsigned>>& edgeStack, std::pair<unsigned, unsigned> edge, std::vector<std::vector<unsigned>>& components) {
  std::pair<unsigned, unsigned> current;
  do {
    current = edgeStack.top();
    edgeStack.pop();
    components[components.size() - 1].push_back(current.first);
    components[components.size() - 1].push_back(current.second);
  } while(current.first != edge.first || current.second != edge.second);

  std::vector<unsigned>& lastComponent = components[components.size() - 1];
  std::sort(lastComponent.begin(), lastComponent.end());
  lastComponent.resize(std::unique(lastComponent.begin(), lastComponent.end()) - lastComponent.begin());
}

void bcDFS(unsigned u, std::vector<std::vector<unsigned>>& graph, std::vector<bool>& visited, std::vector<unsigned>& disc,
  std::vector<unsigned>& low, std::vector<int>& parent, std::vector<std::vector<unsigned>>& components, std::stack<std::pair<unsigned, unsigned>>& edgeStack) {
  static int time = 0;
  time++;
  visited[u - 1] = true;
  disc[u - 1] = time;
  low[u - 1] = time;
  for (unsigned v : graph[u - 1]) {
    if (!visited[v - 1]) {
      parent[v - 1] = u;
      edgeStack.push(std::make_pair(u, v));
      bcDFS(v, graph, visited, disc, low, parent, components, edgeStack);
      low[u - 1] = std::min(low[u - 1], low[v - 1]);
      if (low[v - 1] >= disc[u - 1]) {
        components.push_back(std::vector<unsigned>());
        bcGet(edgeStack, std::make_pair(u, v), components);
      }
    } else if (parent[v - 1] != u && disc[v - 1] < disc[u - 1]) {
      edgeStack.push(std::make_pair(u, v));
      low[u - 1] = std::min(low[u - 1], disc[v - 1]);
    }
  }
}

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

  unsigned n, m;
  in >> n >> m;

  std::vector<std::vector<unsigned>> graph = std::vector<std::vector<unsigned>>();
  graph.reserve(n);
  for (unsigned i = 0; i < n; i++) graph.push_back(std::vector<unsigned>());
  for (unsigned i = 0 ; i < m; i++) {
    unsigned v1, v2;
    in >> v1 >> v2;
    graph[v1 - 1].push_back(v2);
    graph[v2 - 1].push_back(v1);
  }

  std::vector<bool> visited = std::vector<bool>();
  visited.reserve(n);
  for (unsigned i = 0; i < n; i++) visited.push_back(false);

  std::vector<unsigned> disc = std::vector<unsigned>();
  disc.reserve(n);
  for (unsigned i = 0; i < n; i++) disc.push_back(0);

  std::vector<unsigned> low = std::vector<unsigned>();
  low.reserve(n);
  for (unsigned i = 0; i < n; i++) low.push_back(0);

  std::vector<int> parent = std::vector<int>();
  parent.reserve(n);
  for (unsigned i = 0; i < n; i++) parent.push_back(-1);

  std::vector<std::vector<unsigned>> components = std::vector<std::vector<unsigned>>();
  std::stack<std::pair<unsigned, unsigned>> edgeStack = std::stack<std::pair<unsigned, unsigned>>();

  for (unsigned i = 0; i < n; i++) {
    if (!visited[i]) bcDFS(i + 1, graph, visited, disc, low, parent, components, edgeStack);
  }

  out << components.size() << "\n";
  for (auto c : components) {
    for (unsigned v : c) {
      out << v << " ";
    }
    out << "\n";
  }
  return 0;
}