## 10199 - Tourist Guide

Moderator: Board moderators

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

### 10199 - Tourist Guide

Is this problem finding articulation points? I'm doing that but I keep on getting WA

cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:
Yes.

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

ram
New poster
Posts: 30
Joined: Wed Mar 06, 2002 2:00 am
Contact:

### I am getting WA!

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]

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
--
"Everything should be made simple, but not always simpler"

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
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 !
[]s
Mauricio Oliveira Carneiro

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
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...

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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.....
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
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 ...
[]s
Mauricio Oliveira Carneiro

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
then could anyone plz give me some more test cases? Thx in advance.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Contact:

### WA

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...!!!

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am
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

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Contact:
Yah, I repair for disconnected graph.But still WA
Please give me some test data(I/O).
I always getting big big WA......

hijbul_ctg
New poster
Posts: 8
Joined: Sat Apr 19, 2003 5:41 pm
Contact:

### KWAESH

NOT FOR 10199 BUT FOR MY FRIEND Er-FUN(PIAL)

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

PIAL(ma )

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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 ~~
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org