10199 - Tourist Guide

[Subeen]

I also got WA. My program passed all previous sample in/out s in this thread. Please help me to identify my problem. here is the code:
[c]#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define min(a, b) (a < b) ? a : b
#define MAXV 105
#define MAXE 5100

int adj[MAXV][MAXV], dfn[MAXV], L[MAXV], num, n;
int edges[MAXE][2], e;

char ara[MAXV][35];

int get_indx(char s[])
{
for(int i=1; i<=n; i++)
if(!strcmp(ara, s))
return i;
return 0;
}

void art(int u, int v)
{
int w;
dfn = num;
L = num;
num++;

for(w=1; w<=n; w++)
{
if(adj[w])
{
if(!dfn[w])
{
edges[e][0] = u;
edges[e++][1] = w;
art(w, u);
L = min(L, L[w]);
}
else if(w!=v)
L = min(L, dfn[w]);
}
}
}

int comp(const void *a, const void *b)
{
char *x = (char *)a;
char *y = (char *)b;
return strcmp(x, y);
}

void main()
{
char a[35], b[35], ans[MAXV][35];
int points[MAXV];
int i, j, count, u, v, root, r_count, map=0, m;

while(1==scanf("%d", &n) && n)
{
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++) adj[j] = 0;
dfn = 0;
}
for(i=1; i<=n; i++) scanf("%s", ara);
scanf("%d", &m);
while(m--)
{
scanf("%s%s", a, b);
i = get_indx(a);
j = get_indx(b);
adj[j] = adj[j] = 1;
}
e = 0;
num = 1;
art(1, 0);

for(i=1; i<=n; i++) points = 0;
root = 1;
r_count = 0;
count = 0;
for(i=0; i<e; i++)
{
u = edges[0];
if(u==root)
{
r_count++;
continue;
}
if(points) continue;
v = edges[1];
if( L[v] >= dfn)
{
count++;
points = 1;
}
}
if(r_count > 1)
{
count++;
points[root] = 1;
}
if(map) printf("\n");
printf("City map #%d: %d camera(s) found\n", ++map, count);

for(i=1, j=0; i<=n; i++)
if(points)
strcpy(ans[j++], ara[i]);
qsort((void *)ans, j, sizeof(ans[0]), comp);
for(i=0; i<count; i++) printf("%s\n", ans[i]);
}
}[/c]
( I have got 315 AC with almost same code )

[Jan]

Can anyone tell me what is the output of the following input set...

Input:

Code: Select all

5
a
b
c
d
e
4
a b
b c
a d
d c
0

Thanks...

[daveon]

output:

Code: Select all

City map #1: 0 camera(s) found

Nothing helpful. So I guess the error lies in your algorithm.

[indyman]

Can anybody help me out? I am getting WA even though I get correct answers for all examples posted on this topic. What is the program really supposed to do for disconnected graphs? Many people have asked this before on this topic, but it hasnt really been answered yet. I am just wondering if thats where I am doing something wrong.

If I am not doing anything wrong with disconnected graphs, are there any other gotchas besides the alphabetical order?

Also, I am having a trailing extra endl at the end since I use it to insert space between cases. Is that right? I tried both ways - with the extra endl and without - I got WA both times. I am bummed!

Here are the inputs & outputs (all compiled from prior posts under this topic) my code gives me:

Code: Select all

Input:
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
6
a
b
d
c
e
f
7
a b
a d
d c
b d
c e
c f
e f
7
g
f
e
d
c
b
a
6
a b
b c
c d
d e
e f
f g
7
g
f
e
d
c
b
a
7
a b
b c
c d
d e
e f
f g
g a
7
g
f
e
d
c
b
a
5
b c
c d
d e
e f
f g
6
a
b
c
d
e
f
5
a b
a f
c d
c e
d e
5
a
b
c
d
e
4
a b
b c
a d
d c 
0 

Code: Select all

Output:
City map #1: 1 camera(s) found
sugarloaf

City map #2: 1 camera(s) found
sambodromo

City map #3: 2 camera(s) found
c
d

City map #4: 5 camera(s) found
b
c
d
e
f

City map #5: 0 camera(s) found

City map #6: 1 camera(s) found
f

City map #7: 2 camera(s) found
a
c

City map #8: 0 camera(s) found

[Jan]

My accepted code returns...

Output:

Code: Select all

City map #1: 1 camera(s) found
sugarloaf

City map #2: 1 camera(s) found
sambodromo

City map #3: 2 camera(s) found
c
d

City map #4: 5 camera(s) found
b
c
d
e
f

City map #5: 0 camera(s) found

City map #6: 4 camera(s) found
c
d
e
f

City map #7: 1 camera(s) found
a

City map #8: 0 camera(s) found

Dont worry about presentation. If your output format is not correct you will get accepted(presentation error).
And if the graph is disconnected just print the articulations from each connected subgrapth.
Hope these help.

[indyman]

Jan,

Thanks for the output from your accepted code. I fxed my code and am getting the same answers for this input as you posted. Still WA. Any ideas as to which test cases might help? I am bummed.

[Jan]

Try the cases...

Input:

Code: Select all

6
a
b
c
d
e
f
3
a f
b c
e d
6
a
b
c
d
e
f
6
a f
b c
e d
f e
a d
b d
6
x
y
z
a
b
c
0
6
x
y
z
a
b
c
7
x y
y z
z x
a b
b c
a c
a z
0

Output:

Code: Select all

City map #1: 0 camera(s) found

City map #2: 2 camera(s) found
b
d

City map #3: 0 camera(s) found

City map #4: 2 camera(s) found
a
z

Hope these help. If your code passes, post your code.

[indyman]

Hi Jan,

My code passed the above test cases you posted:
This is the output:

Code: Select all

City map #1: 0 camera(s) found

City map #2: 2 camera(s) found
b
d

City map #3: 0 camera(s) found

City map #4: 2 camera(s) found
a
z

This is my code... Hope you can help..

Code: Select all

Code Removed

Hope you can help.... Thanks...

[indyman]

Jan,

I think the following test case also might help me figure out whats wrong:

Input:

Code: Select all

6
a
b
c
d
e
f
4
a b
a f
c d
d e
0

The output I get, is:

Code: Select all

City map #1: 1 camera(s) found
a

Although, if you make the graph, its like this:

Code: Select all

b ------ a ------- f

c ------ d ------- e

where there are two disjoint parts of the graph. Shouldnt the answer be

Code: Select all

City map #1: 2 camera(s) found
a
d

What does your code give?

[Jan]

My code returns

Code: Select all

City map #1: 2 camera(s) found
a
d

which is correct.

[indyman]

Just as I thought. Thanks man. If you get any insights from my code, please let me know. I am thinking theres something wrong with the way I compute my low[] in the function low2[].

Thanks.

[indyman]

Jan,

Thank you very much for the test cases and advice. I figured out the error in my code. In my implementation of articulation points, I was calculating low using regular edges instead of the edges from the DFS tree. Doh! )

Thanks a lot once again!

[emotional blind]

I have no idea for which input my code fails..
I am getting WAs

Code: Select all

Removed after got Accepted

[emotional blind]

I hv found my mistake..
Thanks to Sunny.

[raymond-luxury-yacht]

Is there any problem with finding articulation points just by removing the point from the graph and counting if the number of graph components increased? My program works fine for all the input mentioned in this topic, but still got WA