Cod sursa(job #2197028)

Utilizator georgeromanGeorge Roman georgeroman Data 20 aprilie 2018 22:40:18
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.93 kb
#include <fstream>
#include <stack>
#include <vector>

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

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

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

  std::stack<unsigned> s = std::stack<unsigned>();

  std::vector<bool> initialVisited = std::vector<bool>();
  initialVisited.reserve(n);
  for (unsigned i = 0; i < n; i++) initialVisited.push_back(false);
  unsigned currentUnvisited = 1;
  unsigned numVisited = 0;
  std::stack<unsigned> firstDFSStack = std::stack<unsigned>();
  while (numVisited < n) {
    firstDFSStack.push(currentUnvisited);
    initialVisited[currentUnvisited - 1] = true;
    do { currentUnvisited++; } while (initialVisited[currentUnvisited - 1] && currentUnvisited < n);
    numVisited++;
    while (!firstDFSStack.empty()) {
      unsigned current = firstDFSStack.top();
      bool hasNeighbors = false;
      for (unsigned v : graph[current - 1]) {
        if (!initialVisited[v - 1]) {
          if (v == currentUnvisited) {
            do { currentUnvisited++; } while (initialVisited[currentUnvisited - 1] && currentUnvisited < n);
          }
          hasNeighbors = true;
          firstDFSStack.push(v);
          initialVisited[v - 1] = true;
          numVisited++;
          break;
        }
      }
      if (!hasNeighbors) {
        s.push(firstDFSStack.top());
        firstDFSStack.pop();
      }
    }
  }

  std::vector<std::vector<unsigned>> components = std::vector<std::vector<unsigned>>();
  std::vector<bool> visited = std::vector<bool>();
  visited.reserve(n);
  for (unsigned i = 0; i < n; i++) visited.push_back(false);
  while (!s.empty()) {
    unsigned current = s.top();
    if (!visited[current - 1]) {
      components.push_back(std::vector<unsigned>());
      visited[current - 1] = true;
      std::stack<unsigned> dfsStack = std::stack<unsigned>();
      dfsStack.push(current);
      while (!dfsStack.empty()) {
        unsigned curr = dfsStack.top();
        bool hasNeighbors = false;
        for (unsigned v : tgraph[curr - 1]) {
          if (!visited[v - 1]) {
            visited[v - 1] = true;
            dfsStack.push(v);
            hasNeighbors = true;
            break;
          }
        }
        if (!hasNeighbors) {
          dfsStack.pop();
          components[components.size() - 1].push_back(curr);
        }
      }
    }
    s.pop();
  }

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

  return 0;
}