Page 1 of 4

### 10199 - Tourist Guide

Posted: Thu Dec 19, 2002 6:23 am
Is this problem finding articulation points? I'm doing that but I keep on getting WA

Posted: Thu Jan 30, 2003 7:01 am
Yes.

The graph is possibly disconnected, so you may have to run the algorithm more than once.

### I am getting WA!

Posted: Wed Mar 19, 2003 9:20 am
I think I considered disconnected graph also, but still getting WA! Can anybody help. Here is the code

[cpp]
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <map>
#include <iomanip>
#include <vector>
#include <fstream>

using namespace std;

typedef map<string,int> XX;
XX mapper;
typedef map<int,string> LL;
LL mapper2;
int field[100][100];
int color2[100];
int par[100][100];
int chld[100][100];
int dfnum[100],low[100];
int color[100];
int verts,eds;
int dfn;

void DFSer(int I){
int i,j,k;
color=1;
dfnum=low=dfn++;

for(i=0;i<verts;i++){
if(field==1&&color==0) {
chld=1;
par=1;
DFSer(i);
}
}
}

void solver(int I){

int i,j,k;
color2[I]=1;

for(i=0;i<verts;i++)
if(color2[i]==1&&field[I][i]==1) low[I]=min(low[I],dfnum[i]);

for(i=0;i<verts;i++){
if(color2[i]==0&&chld[I][i]==1)
solver(i);
}

for(i=0;i<verts;i++) if(color2[i]==0&&chld[I][i]==1&&low[i]<dfnum[i]) low[I]=min(low[I],low[i]);

color2[I]=0;
}

int main(){
int i,j,k,cases;
vector<int> res;
vector<string> finder;
bool flag;
string temp,temp2;
cases=0;
while(cin>>verts){
if(verts==0) break;
memset(field,0,sizeof(field));
memset(par,0,sizeof(par));
memset(chld,0,sizeof(chld));
for(i=0;i<verts;i++){
cin>>temp;
mapper[temp]=i;
mapper2[i]=temp;
}
cin>>eds;
for(i=0;i<eds;i++){
cin>>temp>>temp2;
j=mapper[temp];
k=mapper[temp2];
field[j][k]=1;
field[k][j]=1;
}
memset(dfnum,0,sizeof(dfnum));
memset(low,0,sizeof(low));
memset(color,0,sizeof(color));
memset(color2,0,sizeof(color2));
dfn=0;
res.clear();
finder.clear();
for(i=0;i<verts;i++){
if(color[i]==0){
DFSer(i);
solver(i);
k=0;
for(j=0;j<verts;j++) if(chld[i][j]==1) k++;
if(k>1) res.push_back(i);
for(k=i+1;k<verts;k++){
for(j=i+1;j<verts;j++){
if(chld[k][j]==1&&low[j]>=dfnum[k]){
chld[k][j]=0;
par[j][k]=0;
field[k][j]=0;
field[j][k]=0;
res.push_back(k);
break;
}
}
}
}
}
cases++;
if(cases>1) cout<<endl;
cout<<"City map #"<<cases<<": "<<res.size()<<" camera(s) found"<<endl;
for(i=0;i<res.size();i++) finder.push_back(mapper2[res[i]]);
sort(finder.begin(),finder.end());
for(i=0;i<finder.size();i++) cout<<finder[i]<<endl;

}
return 0;
}

[/cpp]

Posted: Wed Aug 20, 2003 5:19 pm
please post some input-output
--

Posted: Sat Sep 13, 2003 3:30 am
Here's what you're looking for :

Code: Select all

``````6
sugarloaf
maracana
copacabana
ipanema
lapa
7
ipanema copacabana
copacabana sugarloaf
ipanema sugarloaf
maracana lapa
sugarloaf maracana
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
6
a b
b c
c d
d e
e f
f a
0
``````
and the *ACCEPTED* 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: 0 camera(s) found
``````
Hope this would help !

Posted: Sat Sep 13, 2003 2:17 pm
Thanks a million carneiro! I'd never find my mistake if not for your test case... I missed the part about alphabetical order!

Oh man... let's hope I don't make silly mistakes again...

Posted: Sun Sep 14, 2003 2:57 pm
Excuse me...

Wht should i do if the input graph is disconnected? Always output 0?

p.s. my program can pass the i/o above perfectly. still, wa.....

Posted: Sun Sep 14, 2003 11:45 pm
if you handle the I/O above, then your program is handling correctly disconnected graphs, don't worry about that, your problem may be elsewhere ...

Posted: Mon Sep 15, 2003 10:52 am
then could anyone plz give me some more test cases? Thx in advance.

### WA

Posted: Wed Nov 05, 2003 12:31 pm
I solve 10199 but still WA though all of I/O post in this page are ok.
here is my code without articulation point.
[cpp]

long search(char key[])
{
long i;
for(i=0;i<N;i++)

if(!strcmp(key,s1))return i;
return -1;
}
int main(void)
{
long i,m,x,y,p,kase=0;
freopen("10199.in","r",stdin);
while(scanf("%ld",&N)==1)
{
if(!N)break;
init();
if(kase)printf("\n");
for(i=0;i<N;i++)
scanf("%s",s1);
qsort((void *)s1, N, sizeof(s1[0]), sort_function);
scanf("%ld",&m);
for(i=0;i<m;i++)
{
scanf("%s %s",s,e);
x=search(s);
y=search(e);
mat[x][y]=1;
mat[y][x]=1;
}
p = findArtPoint();
printf("City map #%ld: %ld camera(s) found\n",++kase,p);
for(i=0;i<N;i++)
if(artV)
printf("%s\n",s1);
}
return 0;
}
[/cpp]
My Articulation point is AC for 315.
Plz can anyone help me...!!!

Posted: Wed Nov 05, 2003 8:12 pm
You probably did not consider the case when the graph is not connected.
In 315,on the other hand, you are told that the graph is connected, that's why AC

Posted: Thu Nov 06, 2003 10:45 am
Yah, I repair for disconnected graph.But still WA
Please give me some test data(I/O).
I always getting big big WA......

### KWAESH

Posted: Sat Nov 08, 2003 9:41 pm
NOT FOR 10199 BUT FOR MY FRIEND Er-FUN(PIAL)

WHAT DO YOU WANT ? .....................................
MONEY, FAME OR FRIEND(SPECIALLY GEL)

PIAL(ma )

Posted: Thu Nov 27, 2003 6:16 pm
carneiro wrote:if you handle the I/O above, then your program is handling correctly disconnected graphs, don't worry about that, your problem may be elsewhere ...
It's me again!

I've just got ACC in Q315... still... no luck on 10199...

Plz...... anyone plz help

Posted: Fri Nov 28, 2003 12:21 pm
Acc-ed

My problem is really on "disconnected" graphs...

For those who're still stuck, try the following case:
6
a
b
c
d
e
f
5
a b
a f
c d
c e
d e
0
Output:
City map #1: 1 camera(s) found
a
Have fun ~~