Page 1 of 4

10199 - Tourist Guide

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

Posted: Thu Jan 30, 2003 7:01 am
by cytse
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
by ram
I think I considered disconnected graph also, but still getting WA! Can anybody help. Here is the code

:cry:


[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]


Thanx in advance

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

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

Code: Select all

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
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
by junjieliang
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... :oops:

Posted: Sun Sep 14, 2003 2:57 pm
by Observer
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
by carneiro
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
by Observer
then could anyone plz give me some more test cases? Thx in advance. :wink:

WA

Posted: Wed Nov 05, 2003 12:31 pm
by erfan
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
by Dmytro Chernysh
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
by erfan
Yah, I repair for disconnected graph.But still WA
Please give me some test data(I/O).
I always getting big big WA...... :cry:

KWAESH

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

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

PIAL(ma :evil: )

Posted: Thu Nov 27, 2003 6:16 pm
by Observer
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
by Observer
Acc-ed :D

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 ~~ :)