## Thursday, September 25, 2014

### UVa Problem 459 - Graph Connectivity

Problem:

Solution:

A typical number of connected components problem. If not hinted by the book, I would have implemented some sort of search to find out the components. But I don't have to, all I need is the number of components, which I can easily obtained from the disjoint set union find data structure.

My implementation uses path compression and union by size. I love this data structure every time I use it, it is just amazing simple and amazingly fast to code and run.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=400

#include "UVa459.h"

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int find(int* parents, int toFind)
{
if (parents[toFind] < 0)
{
}
else {
return (parents[toFind] = find(parents, parents[toFind])); /* path compression */
}
}

void union_sets(int* parents, int src, int dst)
{
int srcRoot = find(parents, src);
int dstRoot = find(parents, dst);
if (srcRoot != dstRoot)
{
if (srcRoot < dstRoot) {
parents[srcRoot] = parents[srcRoot] + parents[dstRoot]; /* updating sizes */
parents[dstRoot] = srcRoot;

}
else {
parents[dstRoot] = parents[srcRoot] + parents[dstRoot];
parents[srcRoot] = dstRoot;
}
}
}

int UVa459()
{
int number_of_cases;
cin >> number_of_cases;

for (int c = 0; c < number_of_cases; c++)
{
char max;
cin >> max;
int num_nodes = max - 'A' + 1;
string line;
getline(cin, line); /* consume the blank line */
int* parents = new int[num_nodes];
for (int i = 0; i < num_nodes; i++)
{
parents[i] = -1; /* indicate this is the root node with size 1 */
}
while (true)
{
getline(cin, line);
if (line.length() == 0)
{
break;
}
else
{
int src = line[0] - 'A';
int dst = line[1] - 'A';
union_sets(parents, src, dst);
}
}
int num_connected_components = 0;
for (int i = 0; i < num_nodes; i++)
{
if (parents[i] < 0)
{
num_connected_components++;
}
}
cout << num_connected_components << endl;
if (c != number_of_cases - 1)
{
cout << endl;
}

delete[] parents;
}
return 0;
}