UVA id: 10199 - Tourist Guide

.gitignore

touristGuide
*.swp

makefile

CC=clang
CFLAGS=-lm -lcrypt -O2 -pipe -ansi -DONLINE_JUDGE -Wall -Wextra -pedantic

OUT=touristGuide

$(OUT):

clean:
	rm -f $(OUT)

sampleInput

6
sugarloaf
maracana
copacabana
ipanema
corcovado
lapa
7
ipanema copacabana
copacabana sugarloaf
ipanema sugarloaf
maracana lapa
sugarloaf maracana
corcovado sugarloaf
lapa corcovado
5
guanabarabay
downtown
botanicgarden
colombo
sambodromo
4
guanabarabay sambodromo
downtown sambodromo
sambodromo botanicgarden
colombo sambodromo
0

touristGuide.c

/*
* Max DeLiso
* 9/26/13
* UVA id: 10199 - Tourist Guide
* url: http://uva.onlinejudge.org/external/101/10199.html
* cited:
*   Hopcroft, J.; Tarjan, R. (1973).
*   “Efficient algorithms for graph manipulation”.
*   Communications of the ACM 16: 372–378. doi:10.1145/362248.362272
*/

#ifdef _WIN32
#define _CRT_SECURE_NO_WARNINGS
typedef unsigned char bool;
const bool true = 1;
const bool false = 0;
#else
#include <stdbool.h>
#endif

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stddef.h>
#include <string.h>

/* PREPROCESSOR DEFINITIONS */

#define MAX_CITY_COUNT          100
#define MAX_CITY_NAME_CHARS     30
#define CITY_INVALID            255

#define ERR_INVALID_INPUT       1

#define STATIC_MIN(a,b) ((a<b)?(a):(b))

/* DATA TYPES */

typedef char cityName[MAX_CITY_NAME_CHARS + 2]; /* 2 for padding */
typedef unsigned char city_t;   /* this is big enough for 100 */

struct graph_t {
  city_t V;
  city_t adj[MAX_CITY_COUNT][MAX_CITY_COUNT];
  city_t adjLens[MAX_CITY_COUNT];
};

/* UTILITY PROTOTYPES */

void scanfExpecting(int ret, const int count);

/* GRAPH PROTOTYPES */

void addEdge(const city_t sourceCity,
             const city_t destCity, struct graph_t *graphPtr);

bool checkEdge(const city_t sourceCity,
               const city_t destCity, struct graph_t *graphPtr);

city_t countAdjacent(const city_t sourceCity, struct graph_t *graphPtr);

city_t nthAdjacent(const city_t sourceCity,
                   const city_t index, struct graph_t *graphPtr);

void HopcroftTarjanSequence(struct graph_t *const cityGraph,
                            city_t essential[MAX_CITY_COUNT],
                            city_t * essentialCount);

void biconnect(struct graph_t *const cityGraph,
               city_t * n,
               city_t v,
               city_t u,
               city_t numbers[MAX_CITY_COUNT],
               city_t lowPoints[MAX_CITY_COUNT],
               bool essentialOrds[MAX_CITY_COUNT], city_t * rCs);

int compareCityNames(const void *first, const void *second);

int compareCityOrdinals(const void *first, const void *second);

city_t lookupCity(cityName cnTable[MAX_CITY_COUNT],
                  size_t cityCount, cityName * cn);

bool processCityData(const int cityMapNumber);

/* ENTRY */

int main()
{
  int i;
  for (i = 1; processCityData(i); ++i) ;
  return 0;
}

/* FUNCTION DEFINITIONS */

void scanfExpecting(int ret, const int count)
{
  if (ret != count || ret == EOF) {
    exit(ERR_INVALID_INPUT);
  }
}

void addEdge(const city_t sourceCity,
             const city_t destCity, struct graph_t *graphPtr)
{
  graphPtr->adj[sourceCity][graphPtr->adjLens[sourceCity]++] = destCity;
  graphPtr->adj[destCity][graphPtr->adjLens[destCity]++] = sourceCity;
}

bool checkEdge(const city_t sourceCity,
               const city_t destCity, struct graph_t *graphPtr)
{
  const size_t rowSize = graphPtr->adjLens[sourceCity]; /* must be the same as destCity */

  return
    memchr(graphPtr->adj[sourceCity], (int) destCity, rowSize) ||
    memchr(graphPtr->adj[destCity], (int) sourceCity, rowSize);
}

city_t countAdjacent(const city_t sourceCity, struct graph_t * graphPtr)
{
  return graphPtr->adjLens[sourceCity];
}

city_t nthAdjacent(const city_t sourceCity,
                   const city_t index, struct graph_t * graphPtr)
{
  return graphPtr->adj[sourceCity][index];
}

void HopcroftTarjanSequence(struct graph_t *const cityGraph,
                            city_t essential[MAX_CITY_COUNT],
                            city_t * essentialCount)
{
  city_t n = 0;
  city_t rCs[MAX_CITY_COUNT];
  city_t lowPoints[MAX_CITY_COUNT];
  city_t numbers[MAX_CITY_COUNT];
  bool essentialOrds[MAX_CITY_COUNT];

  city_t w, i;

  memset(rCs, 0, cityGraph->V);
  memset(numbers, CITY_INVALID, cityGraph->V);
  memset(essentialOrds, false, cityGraph->V);

  /* process any remaining vertices */
  for (w = 1; w < cityGraph->V; ++w) {
    if (numbers[w] == CITY_INVALID) {
      biconnect(cityGraph, &n, w, 0, numbers, lowPoints, essentialOrds, rCs);

      n = 0;
    }
  }

  /* pull ordinals out of array */
  *essentialCount = 0;
  for (i = 0; i < cityGraph->V; ++i) {
    if (essentialOrds[i] || rCs[i] >= 2) {
      essential[(*essentialCount)++] = i;
    }
  }
}

void biconnect(struct graph_t *const cityGraph,
               city_t * n,
               city_t v,
               city_t u,
               city_t numbers[MAX_CITY_COUNT],
               city_t lowPoints[MAX_CITY_COUNT],
               bool essentialOrds[MAX_CITY_COUNT], city_t * rCs)
{
  city_t index;
  const city_t vAdjCount = countAdjacent(v, cityGraph);

  /* number v and set lowpoint v to the same */
  numbers[v] = (*n)++;
  lowPoints[v] = numbers[v];

  /* for each neighbor of v */
  for (index = 0; index < vAdjCount; ++index) {
    city_t w = nthAdjacent(v, index, cityGraph);

    /* if w is not yet numbered */
    if (numbers[w] == CITY_INVALID) {
      biconnect(cityGraph, n, w, v, numbers, lowPoints, essentialOrds, rCs);

      lowPoints[v] = STATIC_MIN(lowPoints[v], lowPoints[w]);

      if (lowPoints[w] >= numbers[v]) {
        /* it's root biconnected */
        if (numbers[v] == 0 || numbers[w] == 0) {
          ++rCs[v];
        } else {
          essentialOrds[v] = 1;
        }
      }
    } else if (numbers[w] < numbers[v] && w != u) {
      lowPoints[v] = STATIC_MIN(lowPoints[v], numbers[w]);
    }
  }
}

/* compare two city names.
 * delegates to libc */
int compareCityNames(const void *first, const void *second)
{
  return strcmp((const char *)first, (const char *)second);
}

int compareCityOrdinals(const void *first, const void *second)
{
  signed short sFirst = (signed short)*(city_t *) first;
  signed short sSecond = (signed short)*(city_t *) second;

  return sFirst - sSecond;
}

/* bsearch the city name table and return the matching index.
 * delegates to libc */
city_t lookupCity(cityName cnTable[MAX_CITY_COUNT],
                  size_t cityCount, cityName * cn)
{

  /* bsearch of cnTable for key, returning pointer to matching city */
  /* note: these casts are only required on win32 */
  cityName *cnPtr = (cityName *) bsearch((void *)cn,
                                         (void *)cnTable,
                                         cityCount,
                                         sizeof(cityName),
                                         &compareCityNames);

  /* portably compute index of cn via pointer arithmetic */
  ptrdiff_t arrayOffset = cnPtr - cnTable;
  size_t keyIndex = (size_t) arrayOffset;

  /* this cast is safe because MAX_CITY_COUNT and signedness of city_t */
  return (city_t) keyIndex;
}

bool processCityData(const int cityMapNumber)
{
  int cityCount;
  int routeCount;
  int i;
  struct graph_t cityGraph;
  cityName cityNameList[MAX_CITY_COUNT];

  city_t essential[MAX_CITY_COUNT];
  city_t essentialCount = 0;

  /* scan city count */
  scanfExpecting(scanf("%d", &cityCount), 1);

  /* 0 is sentinel */
  if (cityCount == 0) {
    return false;
  } else if (cityCount < 0 || cityCount == 1 || cityCount == 2
             || cityCount > MAX_CITY_COUNT) {
    exit(ERR_INVALID_INPUT);
  }

  /* read city names */
  for (i = 0; i < cityCount; ++i) {
    scanfExpecting(scanf("%s", ((char *)cityNameList[i])), 1);

    /* if the string read was longer than the maximum, kill the process */
    if (strlen((char *)cityNameList[i]) > MAX_CITY_NAME_CHARS) {
      exit(ERR_INVALID_INPUT);
    }
  }

  /* sort cities lexicographically to speed up subsequent step */
  qsort(cityNameList, (size_t) cityCount, sizeof(cityName), compareCityNames);

  /* scan route count */
  scanfExpecting(scanf("%d", &routeCount), 1);

  /* route count must be a non-negative integer */
  if (routeCount < 0) {
    exit(ERR_INVALID_INPUT);
  }

  /* initialize graph */
  cityGraph.V = (city_t) cityCount;
  memset(cityGraph.adjLens, 0, (size_t) cityCount);

  /* read route names */
  for (i = 0; i < routeCount; ++i) {
    cityName sourceCity;
    cityName destCity;

    city_t sourceIndex;
    city_t destIndex;

    scanfExpecting(scanf("%s", (char *)&sourceCity), 1);
    scanfExpecting(scanf("%s", (char *)&destCity), 1);

    sourceIndex = lookupCity(cityNameList, (size_t) cityCount, &sourceCity);
    destIndex = lookupCity(cityNameList, (size_t) cityCount, &destCity);

    /* add the edge to the city graph */
    addEdge(sourceIndex, destIndex, &cityGraph);
  }

  /* this is the heart of the program */
  HopcroftTarjanSequence(&cityGraph, essential, &essentialCount);

  /* sort the result city ordinals so that the output will be sorted */
  qsort(essential, essentialCount, sizeof(city_t), compareCityOrdinals);

  /* if this is not the first city, print a new line _before_ the output,
   * this way there will be a line between each output set but not after
   * the last one (this function returns before reaching here on the last
   * iteration)
   */
  if (cityMapNumber > 1) {
    printf("\n");
  }

  /* print out the header for this city set */
  printf("City map #%i: %i camera(s) found\n", cityMapNumber, essentialCount);

  /* print out each city name */
  for (i = 0; i < essentialCount; ++i) {
    printf("%s\n", cityNameList[essential[i]]);
  }

  /* true means continue attempting to process records */
  return true;
}