Implementation of Tarjan's Strongly connected components algorithm with O(|V| + |E|) time complexity for UVA problem "247 - Calling Circles". I also use hash table with open addressing and linear probing

TarjanSCC.cpp

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <stack>
#include <utility>
using namespace std;
int N, M;
const int TABLE_SIZE = 1000;
stack<int> S;
vector<vector<vector<string> > > answers;

string table[TABLE_SIZE];
bool exists[TABLE_SIZE];
bool visited[TABLE_SIZE];
bool inStack[TABLE_SIZE];
int dfs_num[TABLE_SIZE];
int dfs_low[TABLE_SIZE];
vector<int> G[TABLE_SIZE];
vector<vector<string> > solution;
int counter = 0;

int h(const string &str)
{
    int hash = 0;
    for(int i = 0; i < str.size(); ++i)
    {
        hash += (i+1)*str[i]*23 + 137;
        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)
{
    visited[root] = true;
    inStack[root] = true;
    dfs_num[root] = counter;
    dfs_low[root] = counter;
    ++counter;
    S.push(root);

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

    if(dfs_low[root] == dfs_num[root])
    {
        vector<string> currentComponent;
        int currentNode = -1;
        while(currentNode != root)
        {
            currentNode = S.top(); S.pop();
            inStack[currentNode] = false;
            currentComponent.push_back(table[currentNode]);
        }
        solution.push_back(currentComponent);
    }
}
void read()
{
    fill(table, &table[TABLE_SIZE], "");
    fill(exists, &exists[TABLE_SIZE], false);
    fill(visited, &visited[TABLE_SIZE], false);
    fill(inStack, &inStack[TABLE_SIZE], false);
    for(int i = 0; i < TABLE_SIZE; ++i) G[i].clear();
    solution.clear();
    counter = 0;
    //all ready
    for(int i = 0; i < M; ++i)
    {
        string from, to;
        cin >> from >> to;
        int s1 = insert(from);
        int s2 = insert(to);
        exists[s1] = true;
        exists[s2] = true;
        G[s1].push_back(s2);
    }
    for(int i = 0; i < TABLE_SIZE; ++i)
    {
        if(exists[i] && !visited[i])
        {
            DFS(i);
        }
    }
    answers.push_back(solution);
}
int main()
{
    ios::sync_with_stdio(false);
    while(true)
    {
        cin >> N >> M;
        if(N == 0 && M == 0) break;
        read();
    }
    for(int i = 0; i < answers.size(); ++i)
    {
        cout<<"Calling circles for data set "<<i+1<<":\n";
        for(int j = 0; j < answers[i].size(); ++j)
        {
            //cout<<"Current SCC: ";
            for(int k = 0; k < answers[i][j].size(); ++k)
            {
                cout<<answers[i][j][k];
                if(k < answers[i][j].size() - 1) cout<<", ";
            }
            cout<<'\n';
        }
        if(i < answers.size()-1)cout<<'\n';
    }
    return 0;
}