Re: 10199 - Tourist Guide
Posted: Mon Jul 09, 2012 7:52 pm
Hi All,
My code has correctly solved all the inputs posted here, but it is still getting WA.
It locates all the articulation points in the graph associated to a city, which will later correspond to camera locations.
First, it performs a DFS computing the "low" parameter. Then, the articulation points are the vertices that satisfy either one of the following properties:
1) If it is the root of a DFS tree and has more than 2 child nodes within this tree.
2) If it is an internal node and if its "low" is greater than or equal to its discovery time.
Could you help to find the error in my solution? See the code below.
Best regards.
My code has correctly solved all the inputs posted here, but it is still getting WA.
It locates all the articulation points in the graph associated to a city, which will later correspond to camera locations.
First, it performs a DFS computing the "low" parameter. Then, the articulation points are the vertices that satisfy either one of the following properties:
1) If it is the root of a DFS tree and has more than 2 child nodes within this tree.
2) If it is an internal node and if its "low" is greater than or equal to its discovery time.
Could you help to find the error in my solution? See the code below.
Best regards.
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NIL -1
#define MAX_LEN 30
#define MAX_LOCATIONS 100
typedef enum {
FALSE = 0,
TRUE
} Bool;
enum color {
WHITE,
GRAY,
BLACK
};
#define MIN(a,b) (a<b?a:b)
typedef struct neighbor {
int v;
struct neighbor *next;
} Neighbor;
typedef Neighbor* Adjacency_list;
typedef struct graph {
Bool directed;
int n, m;
Adjacency_list *adj;
} Graph;
int *color;
int *pi;
int *d;
int *low;
int time;
char C[MAX_LOCATIONS][MAX_LEN+1];
Graph *create_graph(int n, Bool directed)
{
int i;
Graph *G = (Graph *) malloc(sizeof(Graph));
G->n = n;
G->m = 0;
G->directed = directed;
G->adj = (Adjacency_list *) malloc(n * sizeof(Adjacency_list));
for (i = 0; i < n; i++) {
G->adj[i] = NULL;
}
return G;
}
void destroy_graph(Graph *G)
{
int u;
Neighbor *p, *t;
for (u = 0; u < G->n; u++) {
p = G->adj[u];
while (p != NULL) {
t = p;
p = p->next;
free(t);
}
G->adj[u] = NULL;
}
free(G->adj);
free(G);
}
void __add_edge(Graph *G, int u, int v)
{
Neighbor *p = (Neighbor *) malloc(sizeof(Neighbor));
p->v = v;
p->next = G->adj[u];
G->adj[u] = p;
}
void add_edge(Graph *G, int u, int v)
{
/* loops are not allowed */
if (u == v) return;
__add_edge(G, u, v);
if (!G->directed)
__add_edge(G, v, u);
G->m++;
}
void dfs_visit(Graph *G, int u)
{
Neighbor *p;
color[u] = GRAY;
d[u] = ++time;
low[u] = d[u];
for (p = G->adj[u]; p != NULL; p = p->next) {
if (color[p->v] == WHITE) {
pi[p->v] = u;
dfs_visit(G, p->v);
low[u] = MIN(low[u], low[p->v]);
} else {
if (p->v != pi[u])
low[u] = MIN(low[u], d[p->v]);
}
}
color[u] = BLACK;
}
void dfs(Graph *G)
{
int u;
for (u = 0; u < G->n; u++) {
color[u] = WHITE;
pi[u] = NIL;
}
time = 0;
for (u = 0; u < G->n; u++) {
if (color[u] == WHITE) {
dfs_visit(G, u);
}
}
}
int compute_camera_locations(Graph *G, Bool *camera)
{
int u, num_childs = 0, c;
Neighbor *p;
/* DFS stuff */
color = (int *) malloc(G->n * sizeof(int));
pi = (int *) malloc(G->n * sizeof(int));
d = (int *) malloc(G->n * sizeof(int));
low = (int *) malloc(G->n * sizeof(int));
dfs(G);
/* Now, we mark all the articulations */
for (u = 0; u < G->n; u++) {
camera[u] = FALSE;
}
c = 0;
for (u = 0; u < G->n; u++) {
if (pi[u] == NIL) { /* u is a root, check if it has more than one child nodes */
num_childs = 0;
for (p = G->adj[u]; p != NULL; p = p->next) {
if (pi[p->v] == u)
num_childs++;
}
if (num_childs > 1) {
camera[u] = TRUE;
c++;
}
} else { /* u is internal */
for (p = G->adj[u]; p != NULL; p = p->next) {
if (low[p->v] >= d[u]) {
camera[u] = TRUE;
c++;
break;
}
}
}
}
free(color);
free(pi);
free(d);
free(low);
return c;
}
void insertion_sort(int n, char s[][MAX_LEN+1])
{
int i, j;
char tmp[MAX_LEN+1];
for (i = 1; i < n; i++) {
for (j = i; j > 0; j--) {
if (strcmp(s[j], s[j-1]) < 0) {
strcpy(tmp, s[j]);
strcpy(s[j], s[j-1]);
strcpy(s[j-1], tmp);
}
}
}
}
int loc_id(int n, char location[][MAX_LEN+1], char *s)
{
int i;
for (i = 0; i < n; i++) {
if (strcmp(s, location[i]) == 0)
return i;
}
return NIL;
}
int main(int argc, char *argv[])
{
int i, u, v, n, m, num_cams, city;
char s1[MAX_LEN+1], s2[MAX_LEN+1];
Bool camera[MAX_LOCATIONS];
Graph *map;
city = 1;
while (1) {
scanf("%d", &n);
if (n == 0) break;
if (n < 3 || n > 100) continue;
if (city > 1)
printf("\n");
/* read locations */
for (i = 0; i < n; i++) {
scanf("%s", C[i]);
}
insertion_sort(n, C);
/* create graph */
map = create_graph(n, FALSE);
scanf("%d", &m);
for (i = 0; i < m; i++) {
scanf("%s %s", s1, s2);
u = loc_id(map->n, C, s1);
v = loc_id(map->n, C, s2);
if (u == NIL || v == NIL) {
fprintf(stderr, "invalid location.\n");
exit(EXIT_FAILURE);
}
add_edge(map, u, v);
}
num_cams = compute_camera_locations(map, camera);
printf("City map #%d: %d camera(s) found\n", city, num_cams);
for (u = 0; u < map->n; u++) {
if (camera[u] == TRUE)
printf("%s\n", C[u]);
}
city++;
destroy_graph(map);
}
return 0;
}
