## Tuesday, December 23, 2014

### UVa Problem 200 - Rare Order

Problem:

Solution:

Suppose ABCE comes before ABDF in the index, we can derive C comes before D, but we can say nothing about the relative order of E and F.

Now we are given a list of relative orders, we need a total order, that will be solved by topological sort.

In this problem we will use Tarjan's solution to do topological sort in linear time. Basically it is Kosaraju's algorithm with only the first phase, because the second phase is unnecessary, we already know every node is a strongly connected component of itself, and the order generated fit our purpose.

Code:

#include "stdafx.h"

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

#include "UVa200.h"

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

using namespace std;

void UVa200_dfs(int current, vector<int>& colors, vector<set<int> > adjacency_list, stack<int>& finishing_order);

int UVa200()
{
string line;
vector<string> index;
while (true)
{
getline(cin, line);
if (line == "#")
{
break;
}
index.push_back(line);
}

// Step 2: Numbering the characters
map<char, int> numbering;
map<int, char> naming;

for (unsigned int i = 0; i < index.size(); i++)
{
string s = index[i];
for (unsigned int c = 0; c < s.length(); c++)
{
if (numbering.find(s[c]) == numbering.end())
{
int n = numbering.size();
numbering.insert(pair<char, int>(s[c], n));
naming.insert(pair<int, char>(n, s[c]));
}
}
}

// Step 3: Build the precedence graph
int number_of_nodes = numbering.size();

for (unsigned int i = 1; i < index.size(); i++)
{
string prev = index[i - 1];
string next = index[i];
for (unsigned int c = 0; c < prev.length() && c < next.length(); c++)
{
if (prev[c] != next[c])
{
break;
}
}
}

// Step 4: DFS for topological sort
vector<int> colors;
stack<int> finishing_order;
colors.resize(number_of_nodes);
for (int i = 0; i < number_of_nodes; i++)
{
colors[i] = 0;
}

for (int i = 0; i < number_of_nodes; i++)
{
if (colors[i] == 0)
{
}
}

while (finishing_order.size() > 0)
{
cout << naming[finishing_order.top()];
finishing_order.pop();
}
cout << endl;

return 0;
}

void UVa200_dfs(int current, vector<int>& colors, vector<set<int> > adjacency_list, stack<int>& finishing_order)
{
colors[current] = 1;
{
int neighbor = *ni;
if (colors[neighbor] == 0)
{
}