Finding the Articulation points (cut vertexes) in a graph using Tarjan's algorithm with O(|V| + |E|). I also implement string hashing for the UVa problem "10199 - Tourist Guide"

articulationPoints.cpp

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <utility>
using namespace std;
const int TABLE_SIZE = 10000;

string table[TABLE_SIZE];
bool exists[TABLE_SIZE];
bool visited[TABLE_SIZE];
vector<int> G[TABLE_SIZE];
int dfs_num[TABLE_SIZE];
int dfs_low[TABLE_SIZE];
bool isAP[TABLE_SIZE];
int parent[TABLE_SIZE];
int counter;

int DFSRoot;
int rootChildren;
int N;
vector<vector<string> > answers;
int h(const string &str)
{
    int hash = 0;
    for(int i = 0; i < str.size(); ++i)
    {
        hash += (i+1)*str[i]*23 + 2031;
        hash %= TABLE_SIZE;
    }
    return hash;
}
int insert(const string &str)
{
    int slot = h(str);
    while(table[slot] != "")
    {
        if(table[slot] == str) return slot;
        ++slot;
        slot %= TABLE_SIZE;
    }
    table[slot] = str;
    return slot;
}
void DFS(int root)
{
    dfs_num[root] = counter;
    dfs_low[root] = counter;
    visited[root] = true;
    ++counter;

    for(int i = 0; i < G[root].size(); ++i)
    {
        int child = G[root][i];
        if(!visited[child])
        {
            parent[child] = root;
            if(DFSRoot == root) ++rootChildren;
            DFS(child);
            if(dfs_low[child] >= dfs_num[root])
            {
                isAP[root] = true;
            }
            dfs_low[root] = min(dfs_low[root], dfs_low[child]);
        }
        else if(child != parent[root])
        {
            dfs_low[root] = min(dfs_low[root], dfs_num[child]);
        }
    }

}
void read()
{
    counter = 0;
    for(int i = 0; i < TABLE_SIZE; ++i) G[i].clear();
    fill(table, &table[TABLE_SIZE], "");
    fill(exists, &exists[TABLE_SIZE], false);
    fill(visited, &visited[TABLE_SIZE], false);
    fill(dfs_num, &dfs_num[TABLE_SIZE], 0);
    fill(isAP, &isAP[TABLE_SIZE], false);
    fill(parent, &parent[TABLE_SIZE], -1);
    //all ready
    int R;
    for(int i = 0; i < N; ++i)
    {
        string city;
        cin >> city;
        int slot = insert(city);
        exists[slot] = true;
    }
    cin >> R;
    for(int i = 0; i < R; ++i)
    {
        string from, to;
        cin >> from >> to;
        int s1 = insert(from);
        int s2 = insert(to);
        G[s1].push_back(s2);
        G[s2].push_back(s1);
    }
    for(int i = 0; i < TABLE_SIZE; ++i)
    {
        if(exists[i] && !visited[i])
        {
            DFSRoot = i;
            rootChildren = 0;
            DFS(i);
            isAP[i] = rootChildren > 1;
        }
    }
    //collect solutions
    vector<string> solution;
    for(int i = 0; i < TABLE_SIZE; ++i)
    {
        if(exists[i] && isAP[i]) solution.push_back(table[i]);
    }
    sort(solution.begin(), solution.end());
    answers.push_back(solution);
}
int main()
{
    ios::sync_with_stdio(false);
    while(true)
    {
        cin >> N;
        if(N == 0) break;
        read();
    }
    for(int i = 0; i < answers.size(); ++i)
    {
        cout<<"City map #"<<i+1<<": "<<answers[i].size()<<" camera(s) found\n";
        for(int j = 0; j < answers[i].size(); ++j)
        {
            cout<<answers[i][j]<<'\n';
        }
        if(i < answers.size()-1)cout<<'\n';
    }
    return 0;
}