## Monday, December 22, 2014

### UVa Problem 10731 - Test

Problem:

Solution:

By modeling the user prefer A to B as a edge in a directed graph, we can easily see this problem asks for strongly connected components. We will use Tarjan's algorithm for this problem.

One catch to look for: When we compute Low[v] for a node, we don't just look for back edges, we look for edges that links to a node that is currently in the stack, the code shown on the website is explicit about that, and there is also someone commenting about that, but it was never explained why we need those edges.

Consider the graph
1 -> 2
2 -> 1
1 -> 3
3 -> 2

The DFS yields

1 -> 2
2 -> 1 (back track)
1 -> 3
3 -> 2 (at this point we need to make sure low[3] != num[3], or otherwise we think 3 is a strongly connected component of its own, which it isn't.

As a side note - the code is pretty long - there is a lot of conversions and sorting required in this problem.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1672

#include "UVa10731.h"

// #define LOG

#include <iostream>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int UVa10731_number(map<char, int>& numbering, map<int, char>& naming, char c);
void UVa10731_add_edge(map<char, set<char> >& input_graph, char from, char to);
void UVa10731_dfs(int parent, int current, int& dfs_current_num, vector<vector<int> >& adjacency_list, vector<int>& colors, vector<int>& dfs_num, vector<int>& dfs_low, stack<int>& strongly_connected_nodes, vector<bool>& inStack, map<int, char>& naming, vector<vector<char> >& result);
bool UVa10731_order(vector<char> first, vector<char> second);

int UVa10731()
{
int test_case_number = 0;
while (true)
{
test_case_number++;

int number_of_questions;
cin >> number_of_questions;
if (number_of_questions == 0)
{
break;
}

map<char, set<char> > input_graph;
map<char, int> numbering;
map<int, char> naming;

for (int q = 0; q < number_of_questions; q++)
{
char c1, c2, c3, c4, c5;
char ans;
cin >> c1 >> c2 >> c3 >> c4 >> c5 >> ans;

// Map character to number
UVa10731_number(numbering, naming, c1);
UVa10731_number(numbering, naming, c2);
UVa10731_number(numbering, naming, c3);
UVa10731_number(numbering, naming, c4);
UVa10731_number(numbering, naming, c5);
UVa10731_number(numbering, naming, ans);

if (c1 != ans) { UVa10731_add_edge(input_graph, ans, c1); }
if (c2 != ans) { UVa10731_add_edge(input_graph, ans, c2); }
if (c3 != ans) { UVa10731_add_edge(input_graph, ans, c3); }
if (c4 != ans) { UVa10731_add_edge(input_graph, ans, c4); }
if (c5 != ans) { UVa10731_add_edge(input_graph, ans, c5); }
}

// Step 2: Copy the graph for running the algorithm
int number_of_nodes = numbering.size();

for (map<char, set<char> >::iterator gi = input_graph.begin(); gi != input_graph.end(); gi++)
{
int from = UVa10731_number(numbering, naming, gi->first);
for (set<char>::iterator ni = gi->second.begin(); ni != gi->second.end(); ni++)
{
int to = UVa10731_number(numbering, naming, *ni);
}
}

#ifdef LOG
cout << "digraph{" << endl;
for (unsigned int src = 0; src < adjacency_list.size(); src++)
{
for (unsigned int dst_index = 0; dst_index < adjacency_list[src].size(); dst_index++)
{
cout << naming[src] << "->" << naming[dst] << ";" << endl;
}
}
cout << "}" << endl;
#endif

// Step 3: Run the strongly connected component algorithm
vector<int> colors;
vector<bool> inStack;
vector<int> dfs_num; // The dfs visit number
vector<int> dfs_low; // The lowest number reachable by the node by following tree edges and at most one edges in stack
colors.resize(number_of_nodes);
inStack.resize(number_of_nodes);
dfs_num.resize(number_of_nodes);
dfs_low.resize(number_of_nodes);
for (int i = 0; i < number_of_nodes; i++)
{
// white
colors[i] = 0;
inStack[i] = false;
dfs_num[i] = 0;
dfs_low[i] = 0;
}

int dfs_current_num = 0;
vector<vector<char> > result;
for (int i = 0; i < number_of_nodes; i++)
{
stack<int> strongly_connected_nodes;
UVa10731_dfs(-1, i, dfs_current_num, adjacency_list, colors, dfs_num, dfs_low, strongly_connected_nodes, inStack, naming, result);
}

#ifdef LOG
for (int i = 0; i < number_of_nodes; i++)
{
for (int j = 0; j < number_of_nodes; j++)
{
if (dfs_num[j] == i)
{
cout << naming[j] << " : " << dfs_num[j];

for (int k = 0; k < number_of_nodes; k++)
{
if (dfs_num[k] == dfs_low[j])
{
cout << "/" << dfs_low[j] << " (" << naming[k] << ")" << endl;
}
}
}
}
}
#endif

// Step 4: Output
for (vector<vector<char> >::iterator ri = result.begin(); ri != result.end(); ri++)
{
sort(ri->begin(), ri->end());
}
sort(result.begin(), result.end(), UVa10731_order);

if (test_case_number != 1)
{
cout << endl;
}
for (vector<vector<char> >::iterator ri = result.begin(); ri != result.end(); ri++)
{
for (unsigned si = 0; si < ri->size(); si++)
{
if (si != 0)
{
cout << " ";
}
cout << (*ri)[si];
}
cout << endl;
}
}
return 0;
}

bool UVa10731_order(vector<char> first, vector<char> second)
{
return first[0] < second[0];
}

void UVa10731_dfs(int parent, int current, int& dfs_current_num, vector<vector<int> >& adjacency_list, vector<int>& colors, vector<int>& dfs_num, vector<int>& dfs_low, stack<int>& strongly_connected_nodes, vector<bool>& inStack, map<int, char>& naming, vector<vector<char> >& result)
{
if (colors[current] != 0)
{
return;
}
strongly_connected_nodes.push(current);
inStack[current] = true;

colors[current] = 1; // gray
dfs_num[current] = dfs_current_num;
dfs_low[current] = dfs_current_num;
dfs_current_num++;

{
int neighbor = *ni;
if (colors[neighbor] == 0)
{
#ifdef LOG
cout << "Tree edge found:" << naming[current] << "->" << naming[neighbor] << ";" << endl;
#endif
UVa10731_dfs(current, neighbor, dfs_current_num, adjacency_list, colors, dfs_num, dfs_low, strongly_connected_nodes, inStack, naming, result);
dfs_low[current] = min(dfs_low[current], dfs_low[neighbor]);
}
else if (inStack[neighbor])
{
#ifdef LOG
cout << "Back edge found:" << naming[current] << "->" << naming[neighbor] << endl;
#endif
dfs_low[current] = min(dfs_low[current], dfs_num[neighbor]);
}
else
{
#ifdef LOG
cout << "Forward/cross edge found:" << naming[current] << "->" << naming[neighbor] << endl;
#endif
}
}

colors[current] = 2; // black

if (dfs_low[current] == dfs_num[current])
{
vector<char> strongly_connected_component;
while (true)
{
int top = strongly_connected_nodes.top();
strongly_connected_component.push_back(naming[top]);
inStack[top] = false;
strongly_connected_nodes.pop();
if (top == current)
{
break;
}
}
result.push_back(strongly_connected_component);
}
}

int UVa10731_number(map<char, int>& numbering, map<int, char>& naming, char c)
{
map<char, int>::iterator probe = numbering.find(c);
if (probe == numbering.end())
{
int number = numbering.size();
numbering.insert(pair<char, int>(c, number));
naming.insert(pair<int, char>(number, c));
return number;
}
else
{
return probe->second;
}
}

void UVa10731_add_edge(map<char, set<char> >& input_graph, char from, char to)
{
map<char, set<char> >::iterator probe = input_graph.find(from);
if (probe == input_graph.end())
{
set<char> neighbor;
neighbor.insert(to);
input_graph.insert(pair<char, set<char> >(from, neighbor));
}
else
{
probe->second.insert(to);
}
}