Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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) {
- std::vector<int> current_child_index(N, 0);
- stack<int> S;
- S.emplace(root);
- while (!S.empty()) {
- int node = S.top();
- const int child_index = current_child_index[node];
- if (child_index >= graph[node].size()) {
- S.pop();
- continue;
- }
- int child = graph[node][child_index];
- if (child == parent[node]) {
- current_child_index[node]++;
- continue;
- }
- if (parent[child] == -1) {
- parent[child] = node;
- entry[child] = time++;
- farthest_ancestor[child] = child;
- num_children[node]++;
- S.emplace(child);
- continue;
- }
- if (parent[child] == node) {
- if (entry[farthest_ancestor[child]] < entry[farthest_ancestor[node]]) {
- farthest_ancestor[node] = farthest_ancestor[child];
- }
- } else if (entry[child] < entry[node]) {
- if (entry[child] < entry[farthest_ancestor[node]]) {
- farthest_ancestor[node] = child;
- }
- }
- current_child_index[node]++;
- }
- }
Add Comment
Please, Sign In to add comment