10199 - Tourist Guide

[junjieliang]

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

[cytse]

Yes.

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

[ram]

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]


Thanx in advance

[anupam]

please post some input-output
--

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

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

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

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

[Observer]

then could anyone plz give me some more test cases? Thx in advance.

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

[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

[erfan]

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]

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

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

PIAL(ma )

[Observer]

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

[Observer]

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