Recursive 10199 - Tourist Guide

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <utility>
#include <iomanip>
#include <bitset>
#include <fstream>
#include <limits>

using namespace std;

typedef long long int64;

class CutVertexFinder {
 public:
  CutVertexFinder(const std::vector<std::vector<int>>& g);
  std::vector<int> GetCutVertices();

 private:
  std::vector<std::vector<int>> graph;
  const int N;

  int time;
  std::vector<int> farthest_ancestor, entry, parent, num_children;

  void DFS(int root);
  void DFSLoop();
  bool IsRoot(int node) { return (parent[node] == node); }
};

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int N;
  int case_no = 0;
  cin >> N;

  while (N > 0) {
    cin.ignore();
    case_no++;

    unordered_map<string, int> city_index;
    std::vector<string> cities(N);
    for (int i = 0; i < N; ++i) {
      cin >> cities[i];
      city_index[cities[i]] = i;
    }

    int M;
    cin >> M;
    cin.ignore();

    std::vector<std::vector<int>> graph(N);
    for (int i = 0; i < M; ++i) {
      string c1, c2;
      cin >> c1 >> c2;

      int u = city_index[c1];
      int v = city_index[c2];

      graph[u].emplace_back(v);
      graph[v].emplace_back(u);
    }

    CutVertexFinder f(graph);
    std::vector<string> camera_cities;
    for (auto&& vertex : f.GetCutVertices()) {
      camera_cities.emplace_back(cities[vertex]);
    }
    sort(camera_cities.begin(), camera_cities.end());

    if (case_no > 1) cout << "\n";
    cout << "City map #" << case_no << ": " << camera_cities.size()
         << " camera(s) found\n";
    for (auto&& city : camera_cities) {
      cout << city << "\n";
    }

    cin >> N;
  }

  return 0;
}

CutVertexFinder::CutVertexFinder(const std::vector<std::vector<int>>& g)
    : graph(g), N(g.size()) {
  time = 0;
  farthest_ancestor.resize(N, -1);
  entry.resize(N, -1);
  parent.resize(N, -1);
  num_children.resize(N, 0);
}

std::vector<int> CutVertexFinder::GetCutVertices() {
  std::vector<int> cut_vertices;

  DFSLoop();

  std::vector<bool> is_cut_node(N, false);
  for (int i = 0; i < N; ++i) {
    if (IsRoot(i)) {
      if (num_children[i] > 1) is_cut_node[i] = true;
    } else {  // Non root
      if (farthest_ancestor[i] == i) {
        if (!IsRoot(parent[i])) {
          is_cut_node[parent[i]] = true;
        }
        if (num_children[i]) {
          is_cut_node[i] = true;
        }
      } else if (farthest_ancestor[i] == parent[i]) {
        if (!IsRoot(parent[i])) {
          is_cut_node[parent[i]] = true;
        }
      }
    }
  }

  for (int i = 0; i < N; ++i) {
    if (is_cut_node[i]) cut_vertices.emplace_back(i);
  }
  return cut_vertices;
}

void CutVertexFinder::DFSLoop() {
  for (int i = 0; i < N; ++i) {
    if (parent[i] == -1) {
      parent[i] = i;
      entry[i] = time++;
      farthest_ancestor[i] = i;

      DFS(i);
    }
  }
}

void CutVertexFinder::DFS(int root) {
  for (auto&& child : graph[root]) {
    if (child == parent[root]) continue;

    if (parent[child] == -1) {
      // Tree edge
      parent[child] = root;
      entry[child] = time++;
      farthest_ancestor[child] = child;

      num_children[root]++;
      DFS(child);

      if (entry[farthest_ancestor[child]] < entry[farthest_ancestor[root]]) {
        farthest_ancestor[root] = farthest_ancestor[child];
      }
    } else if (entry[child] < entry[root]) {
      // Back edge
      if (entry[child] < entry[farthest_ancestor[root]]) {
        farthest_ancestor[root] = child;
      }
    }
  }
}