Page 2 of 4

Posted: Sat Mar 20, 2004 9:25 am
by 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 )

Posted: Sun Jul 17, 2005 8:37 pm
by 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...

Posted: Mon Dec 26, 2005 12:30 am
by daveon
output:

Code: Select all

City map #1: 0 camera(s) found
Nothing helpful. So I guess the error lies in your algorithm.

Posted: Thu Nov 30, 2006 12:42 pm
by 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

:oops: :oops:

Posted: Thu Nov 30, 2006 12:50 pm
by 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.

Posted: Thu Nov 30, 2006 10:43 pm
by 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.

Posted: Fri Dec 01, 2006 1:06 am
by 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.

Posted: Fri Dec 01, 2006 1:45 am
by 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...

Posted: Fri Dec 01, 2006 2:01 am
by 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?

Posted: Fri Dec 01, 2006 2:04 am
by Jan
My code returns

Code: Select all

City map #1: 2 camera(s) found
a
d
which is correct.

Posted: Fri Dec 01, 2006 2:10 am
by 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.

Posted: Fri Dec 01, 2006 10:37 am
by 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!

Posted: Thu Mar 01, 2007 5:35 am
by emotional blind
I have no idea for which input my code fails..
I am getting WAs

Code: Select all

Removed after got Accepted

Posted: Thu Mar 01, 2007 7:44 am
by emotional blind
I hv found my mistake..
Thanks to Sunny.

Posted: Fri Mar 02, 2007 10:42 pm
by 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 :-?