10199 - Tourist Guide

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

uirapuru
New poster
Posts: 1
Joined: Sat Jul 07, 2012 5:15 am

Re: 10199 - Tourist Guide

Hi All,

My code has correctly solved all the inputs posted here, but it is still getting WA.
It locates all the articulation points in the graph associated to a city, which will later correspond to camera locations.

First, it performs a DFS computing the "low" parameter. Then, the articulation points are the vertices that satisfy either one of the following properties:
1) If it is the root of a DFS tree and has more than 2 child nodes within this tree.
2) If it is an internal node and if its "low" is greater than or equal to its discovery time.

Could you help to find the error in my solution? See the code below.

Best regards.

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NIL -1
#define MAX_LEN 30
#define MAX_LOCATIONS 100

typedef enum {
FALSE = 0,
TRUE
} Bool;

enum color {
WHITE,
GRAY,
BLACK
};

#define MIN(a,b) (a<b?a:b)

typedef struct neighbor {
int v;
struct neighbor *next;
} Neighbor;

typedef Neighbor* Adjacency_list;

typedef struct graph {
Bool directed;
int n, m;
Adjacency_list *adj;
} Graph;

int *color;
int *pi;
int *d;
int *low;
int time;
char C[MAX_LOCATIONS][MAX_LEN+1];

Graph *create_graph(int n, Bool directed)
{
int i;
Graph *G = (Graph *) malloc(sizeof(Graph));
G->n = n;
G->m = 0;
G->directed = directed;
G->adj = (Adjacency_list *) malloc(n * sizeof(Adjacency_list));
for (i = 0; i < n; i++) {
G->adj[i] = NULL;
}
return G;
}

void destroy_graph(Graph *G)
{
int u;
Neighbor *p, *t;
for (u = 0; u < G->n; u++) {
p = G->adj[u];
while (p != NULL) {
t = p;
p = p->next;
free(t);
}
G->adj[u] = NULL;
}
free(G->adj);
free(G);
}

void __add_edge(Graph *G, int u, int v)
{
Neighbor *p = (Neighbor *) malloc(sizeof(Neighbor));
p->v = v;
p->next = G->adj[u];
G->adj[u] = p;
}

void add_edge(Graph *G, int u, int v)
{
/* loops are not allowed */
if (u == v) return;

__add_edge(G, u, v);
if (!G->directed)
__add_edge(G, v, u);

G->m++;
}

void dfs_visit(Graph *G, int u)
{
Neighbor *p;
color[u] = GRAY;
d[u] = ++time;
low[u] = d[u];

for (p = G->adj[u]; p != NULL; p = p->next) {
if (color[p->v] == WHITE) {
pi[p->v] = u;
dfs_visit(G, p->v);
low[u] = MIN(low[u], low[p->v]);
} else {
if (p->v != pi[u])
low[u] = MIN(low[u], d[p->v]);
}
}
color[u] = BLACK;
}

void dfs(Graph *G)
{
int u;

for (u = 0; u < G->n; u++) {
color[u] = WHITE;
pi[u] = NIL;
}
time = 0;
for (u = 0; u < G->n; u++) {
if (color[u] == WHITE) {
dfs_visit(G, u);
}
}
}

int compute_camera_locations(Graph *G, Bool *camera)
{
int u, num_childs = 0, c;
Neighbor *p;

/* DFS stuff */
color = (int *) malloc(G->n * sizeof(int));
pi = (int *) malloc(G->n * sizeof(int));
d = (int *) malloc(G->n * sizeof(int));
low = (int *) malloc(G->n * sizeof(int));

dfs(G);

/* Now, we mark all the articulations */
for (u = 0; u < G->n; u++) {
camera[u] = FALSE;
}

c = 0;
for (u = 0; u < G->n; u++) {
if (pi[u] == NIL) { /* u is a root, check if it has more than one child nodes */
num_childs = 0;
for (p = G->adj[u]; p != NULL; p = p->next) {
if (pi[p->v] == u)
num_childs++;
}
if (num_childs > 1) {
camera[u] = TRUE;
c++;
}
} else { /* u is internal */
for (p = G->adj[u]; p != NULL; p = p->next) {
if (low[p->v] >= d[u]) {
camera[u] = TRUE;
c++;
break;
}
}
}
}

free(color);
free(pi);
free(d);
free(low);

return c;
}

void insertion_sort(int n, char s[][MAX_LEN+1])
{
int i, j;
char tmp[MAX_LEN+1];

for (i = 1; i < n; i++) {
for (j = i; j > 0; j--) {
if (strcmp(s[j], s[j-1]) < 0) {
strcpy(tmp, s[j]);
strcpy(s[j], s[j-1]);
strcpy(s[j-1], tmp);
}
}
}
}

int loc_id(int n, char location[][MAX_LEN+1], char *s)
{
int i;
for (i = 0; i < n; i++) {
if (strcmp(s, location[i]) == 0)
return i;
}
return NIL;
}

int main(int argc, char *argv[])
{
int i, u, v, n, m, num_cams, city;
char s1[MAX_LEN+1], s2[MAX_LEN+1];
Bool camera[MAX_LOCATIONS];
Graph *map;

city = 1;
while (1) {
scanf("%d", &n);
if (n == 0) break;
if (n < 3 || n > 100) continue;

if (city > 1)
printf("\n");

/* read locations */
for (i = 0; i < n; i++) {
scanf("%s", C[i]);
}

insertion_sort(n, C);

/* create graph */
map = create_graph(n, FALSE);
scanf("%d", &m);
for (i = 0; i < m; i++) {
scanf("%s %s", s1, s2);

u = loc_id(map->n, C, s1);
v = loc_id(map->n, C, s2);
if (u == NIL || v == NIL) {
fprintf(stderr, "invalid location.\n");
exit(EXIT_FAILURE);
}
add_edge(map, u, v);
}

num_cams = compute_camera_locations(map, camera);

printf("City map #%d: %d camera(s) found\n", city, num_cams);
for (u = 0; u < map->n; u++) {
if (camera[u] == TRUE)
printf("%s\n", C[u]);
}
city++;

destroy_graph(map);
}

return 0;
}
``````

Mukit Chowdhury
Learning poster
Posts: 99
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10199 - Tourist Guide

Got WA !!!! Would anyone please give me some sample input ???

Code: Select all

``````Accepted........ :)
``````
for those who are getting WA !!!

Code: Select all

``````6
a
b
c
d
e
f
3
a b
c d
e f
0
``````
output must be 0.....

hami
New poster
Posts: 4
Joined: Thu Apr 25, 2013 9:12 pm

Re: 10199 - Tourist Guide

Hello,
I am problem with submittion of my code - WA.
I have tried all of IO what has been written here and my program returned correct answer.
Could anyone help me?
It could be kind of confusing, because name of method, etc... is written in Czech

Code: Select all

``````
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
//import java.util.Scanner;

import java.util.Arrays;

//City map #1: 1 camera(s) found

public class Main {

//private static Scanner sc = new Scanner(System.in);
private static BufferedReader bfr;
static int pocetSpoju =1;
static DfsMatice base;
static int pocetSub;
static String vystup = "";
static int pocitadloMest=0;
static int pocitadloKrizovatek=0;
static String localVystup="";

static void zpracovani(int pocetMest) throws IOException {
pocitadloMest++;
pocitadloKrizovatek=0;
localVystup="";
String vstup = new String();
for(int i = 0 ; i < pocetMest  ; i++){
vstup = vstup + bfr.readLine().trim()+" ";
}
//vstup = vstup + bfr.readLine().trim();
//	System.out.println(vstup.trim());
String [] poleVstupu = vstup.trim().split(" ");
Arrays.sort(poleVstupu);
base.vytvoreniUzlu(poleVstupu);
pocetSpoju = Integer.valueOf(bfr.readLine().trim());
//	System.out.println("pocetSpoju"+pocetSpoju);
//bfr.readLine();
for(int i = 0 ; i<pocetSpoju ; i++){
base.vytvoreniSpojeMaticeObousmerna(bfr.readLine().trim());
}
base.vytvoreniOrigMtice();
//	base.vypisMaticeorig();
//base.vypisMatice();
base.prohledDoHloubky(0);
pocetSub =base.pocetSubGrafu;
//System.out.println(pocetSub);
base.prebileni();
for(int i = 0 ; i<poleVstupu.length ; i++){
vyhodnoceni(poleVstupu[i]);
}
vystup = vystup+"City map #"+pocitadloMest+": "+pocitadloKrizovatek+" camera(s) found"+"\n"+localVystup+"\n";
}
static void vyhodnoceni(String vyhod) {
base.odeberSpoj(vyhod);
base.prohledDoHloubky(0);
//base.vypisMatice();
//base.vypisMaticeorig();
////System.out.println(base.pocetSubGrafu);
//	System.out.println("base.pocetSubGrafu "+base.pocetSubGrafu+" "+"pocetSub "+pocetSub);
if(base.pocetSubGrafu>(pocetSub+1)){
localVystup = localVystup+vyhod+"\n";
pocitadloKrizovatek++;
}
base.prebileni();
base.origMatice();
}
public static void main(String[] args) throws NumberFormatException, IOException {
bfr = new BufferedReader(new InputStreamReader(System.in));
base = new DfsMatice();
int pocet = 0;
while(true){
pocet = Integer.valueOf(bfr.readLine().trim());
//System.out.println("pocet"+pocet);
if(pocet!=0){
zpracovani(pocet);		}
else{
break;			}		}

//	System.out.print(vystup.trim());
System.out.print(vystup);
}
}
class Prvek {
public String nazev;
public Hrana hrana;
//Prvek top;
public String color;
public int vzdalenost;
public int predchudce;
public int objeven;
public int dokoncen;
Prvek(String nazev) {
this.nazev = nazev;
this.hrana = null;
this.color = "White";
this.vzdalenost = Integer.MAX_VALUE;
this.predchudce = -1;
this.objeven = Integer.MAX_VALUE;
this.dokoncen = Integer.MAX_VALUE;
}

}
class Hrana {
public int vrchol;
public Hrana dalsi;

public Hrana (int vrchol) {
this.vrchol = vrchol;
dalsi = null;
} }

class DfsMatice {
private static String[] uzly;
private static int matSousednosti [][];				//matice souslednosti
private static int matSousednostiOrig [][];
public Prvek [] prvky;								//pole objektu
public Prvek [] vystupni;
//	private Prvek prac;
private static int cas = 0;
int pocetSubGrafu;

DfsMatice() {
this.prvky=null;
this.pocetSubGrafu=1;
}
void vytvoreniOrigMtice(){
matSousednostiOrig = new int [uzly.length][uzly.length];
for(int i = 0 ; i < prvky.length ; i++){
for(int j = 0 ; j < prvky.length ; j++){
matSousednostiOrig[i][j]=matSousednosti[i][j];
matSousednostiOrig[j][i]=matSousednosti[j][i];
}
}
}

void vytvoreniUzlu(String[] pole){
uzly = pole;
matSousednosti = new int [uzly.length][uzly.length];
prvky = new Prvek [pole.length];
for(int i = 0 ; i < pole.length ; i++){
prvky[i] = new Prvek(pole[i]);		}
Arrays.toString(pole);
}
void vytvoreniSpojeMaticeObousmerna(String spoj) throws IOException {			//vytvari matici sousednosti
//System.out.println("vytvoreniSpojeMaticeObousmerna: "+spoj);
String [] casti = spoj.trim().split(" ");
if(casti.length>2){
throw new IOException();
}
for(int i = 0 ; i < prvky.length ; i++){
for(int j = 0 ; j < prvky.length ; j++){
if(prvky[i].nazev.equals(casti[0])&&prvky[j].nazev.equals(casti[1])){
matSousednosti[i][j]=1;
matSousednosti[j][i]=1;
return;
}				}
}	}

void vypisMatice() {										//vypise matici sousednosti
System.out.println("");
System.out.println("Vypis matici:");
for(int i = 0 ; i < prvky.length ; i++){
for(int j = 0 ; j < prvky.length ; j++){
System.out.print(" "+matSousednosti[i][j]);
}
System.out.println("");
}				}

void vypisMaticeorig() {										//vypise matici sousednosti
System.out.println("");
System.out.println("Vypis matici orig:");
for(int i = 0 ; i < prvky.length ; i++){
for(int j = 0 ; j < prvky.length ; j++){
System.out.print(" "+matSousednostiOrig[i][j]);
}
System.out.println("");
}				}

int[] sousedi(int vstup){										//slouzi pro for v ohodnoceni
//	System.out.println("sousedi");
int array [] = null;
int pocitadlo = 0;
//System.out.println(matSousednosti[vstup].length);
for(int i = 0 ; i<matSousednosti[vstup].length ; i++){
//System.out.println("for");
//System.out.println(" "+matSousednosti[vstup][i]);
if(matSousednosti[vstup][i]== 1){
//System.out.println("true");
pocitadlo++;
}			}
//System.out.println("pocitadlo "+pocitadlo);
int j = 0;
array = new int [pocitadlo];
for(int k = 0 ; k<matSousednosti[vstup].length ; k++){
if(matSousednosti[vstup][k]==1){
array[j] = k;
j++;
}
}
//	System.out.println("vstup: "+vstup+",  array "+Arrays.toString(array));
return array;
}

void prohledDoHloubky (int s){
pocetSubGrafu=1;
doHloubky(s);

for(int i = 0 ; i < prvky.length ; i++){
if(prvky[i].color == "White"){
doHloubky(i);
pocetSubGrafu++;
}
}
}

void doHloubky (int s) { 									//vytvori predchudce apod.
int v;
prvky[s].color = "Gray";
//prvky[s].vzdalenost = 0;
cas++;
prvky[s].objeven = cas;
int array [] = sousedi(s);
for (int i = 0 ; i < array.length ; i++) {
v = array[i];
if (prvky[v].color == "White") {
prvky[v].predchudce = s;
doHloubky(v);
} 			}
prvky[s].color = "Black";
prvky[s].dokoncen = cas = cas+1;

}
void odeberSpoj(String spoj){
int index=0;
for(int i = 0 ; i< uzly.length ; i++){
if(uzly[i].equals(spoj)){
index = i;
break;
}
}
for(int i = 0 ; i < prvky.length ; i++){
for(int j = 0 ; j < prvky.length ; j++){
if(i==index || j==index){
matSousednosti[i][j]=0;
matSousednosti[j][i]=0;

}				}
}		}
void prebileni(){
for(int i = 0 ; i < prvky.length ; i++){
prvky[i].color = "White";
}
}
void origMatice(){

for(int i = 0 ; i < prvky.length ; i++){
for(int j = 0 ; j < prvky.length ; j++){
matSousednosti[i][j]=matSousednostiOrig[i][j];
matSousednosti[j][i]=matSousednostiOrig[j][i];
}
}
}
}

``````
Thanks

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10199 - Tourist Guide

You should print a blank line between output sets. Don't print an extra blank line at the end.
Check input and AC output for thousands of problems on uDebug!

hami
New poster
Posts: 4
Joined: Thu Apr 25, 2013 9:12 pm

Re: 10199 - Tourist Guide

edit: I have changed output how you wrote, but validator still return WA

Code: Select all

``````
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
//import java.util.Scanner;

import java.util.Arrays;

//City map #1: 1 camera(s) found

public class Main {

//private static Scanner sc = new Scanner(System.in);
private static BufferedReader bfr;
private static PrintStream bwr;
static int pocetSpoju =1;
static DfsMatice base;
static int pocetSub;
static String vystup = "";
static int pocitadloMest=0;
static int pocitadloKrizovatek=0;
static String localVystup="";

static void zpracovani(int pocetMest) throws IOException {
pocitadloMest++;
pocitadloKrizovatek=0;
localVystup="";
String vstup = new String();
for(int i = 0 ; i < pocetMest  ; i++){
vstup = vstup + bfr.readLine().trim()+" ";
}
//vstup = vstup + bfr.readLine().trim();
//	System.out.println(vstup.trim());
String [] poleVstupu = vstup.trim().split(" ");
Arrays.sort(poleVstupu);
base.vytvoreniUzlu(poleVstupu);
pocetSpoju = Integer.valueOf(bfr.readLine().trim());
//	System.out.println("pocetSpoju"+pocetSpoju);
//bfr.readLine();
for(int i = 0 ; i<pocetSpoju ; i++){
base.vytvoreniSpojeMaticeObousmerna(bfr.readLine().trim());
}
base.vytvoreniOrigMtice();
//	base.vypisMaticeorig();
//base.vypisMatice();
base.prohledDoHloubky(0);
pocetSub =base.pocetSubGrafu;
//System.out.println(pocetSub);
base.prebileni();
for(int i = 0 ; i<poleVstupu.length ; i++){
vyhodnoceni(poleVstupu[i]);
}
vystup = vystup+"City map #"+pocitadloMest+": "+pocitadloKrizovatek+" camera(s) found"+"\n"+localVystup+"\n";
}
static void vyhodnoceni(String vyhod) {
base.odeberSpoj(vyhod);
base.prohledDoHloubky(0);
//base.vypisMatice();
//base.vypisMaticeorig();
////System.out.println(base.pocetSubGrafu);
//	System.out.println("base.pocetSubGrafu "+base.pocetSubGrafu+" "+"pocetSub "+pocetSub);
if(base.pocetSubGrafu>(pocetSub+1)){
localVystup = localVystup+vyhod+"\n";
pocitadloKrizovatek++;
}
base.prebileni();
base.origMatice();
}
public static void main(String[] args) throws NumberFormatException, IOException {
bfr = new BufferedReader(new InputStreamReader(System.in));
bwr = new PrintStream(System.out);
base = new DfsMatice();
int pocet = 0;
while(true){
pocet = Integer.valueOf(bfr.readLine().trim());
//System.out.println("pocet"+pocet);
if(pocet!=0){
zpracovani(pocet);		}
else{
break;			}		}

//	System.out.print(vystup.trim());
//System.out.print("\n"+vystup.trim());
bwr.print("\n"+vystup.trim());
}
}
class Prvek {
public String nazev;
public Hrana hrana;
//Prvek top;
public String color;
public int vzdalenost;
public int predchudce;
public int objeven;
public int dokoncen;
Prvek(String nazev) {
this.nazev = nazev;
this.hrana = null;
this.color = "White";
this.vzdalenost = Integer.MAX_VALUE;
this.predchudce = -1;
this.objeven = Integer.MAX_VALUE;
this.dokoncen = Integer.MAX_VALUE;
}

}
class Hrana {
public int vrchol;
public Hrana dalsi;

public Hrana (int vrchol) {
this.vrchol = vrchol;
dalsi = null;
} }

class DfsMatice {
private static String[] uzly;
private static int matSousednosti [][];				//matice souslednosti
private static int matSousednostiOrig [][];
public Prvek [] prvky;								//pole objektu
public Prvek [] vystupni;
//	private Prvek prac;
private static int cas = 0;
int pocetSubGrafu;

DfsMatice() {
this.prvky=null;
this.pocetSubGrafu=1;
}
void vytvoreniOrigMtice(){
matSousednostiOrig = new int [uzly.length][uzly.length];
for(int i = 0 ; i < prvky.length ; i++){
for(int j = 0 ; j < prvky.length ; j++){
matSousednostiOrig[i][j]=matSousednosti[i][j];
matSousednostiOrig[j][i]=matSousednosti[j][i];
}
}
}

void vytvoreniUzlu(String[] pole){
uzly = pole;
matSousednosti = new int [uzly.length][uzly.length];
prvky = new Prvek [pole.length];
for(int i = 0 ; i < pole.length ; i++){
prvky[i] = new Prvek(pole[i]);		}
Arrays.toString(pole);
}
void vytvoreniSpojeMaticeObousmerna(String spoj) throws IOException {			//vytvari matici sousednosti
//System.out.println("vytvoreniSpojeMaticeObousmerna: "+spoj);
String [] casti = spoj.trim().split(" ");
if(casti.length>2){
throw new IOException();
}
for(int i = 0 ; i < prvky.length ; i++){
for(int j = 0 ; j < prvky.length ; j++){
if(prvky[i].nazev.equals(casti[0])&&prvky[j].nazev.equals(casti[1])){
matSousednosti[i][j]=1;
matSousednosti[j][i]=1;
return;
}				}
}	}

void vypisMatice() {										//vypise matici sousednosti
System.out.println("");
System.out.println("Vypis matici:");
for(int i = 0 ; i < prvky.length ; i++){
for(int j = 0 ; j < prvky.length ; j++){
System.out.print(" "+matSousednosti[i][j]);
}
System.out.println("");
}				}

void vypisMaticeorig() {										//vypise matici sousednosti
System.out.println("");
System.out.println("Vypis matici orig:");
for(int i = 0 ; i < prvky.length ; i++){
for(int j = 0 ; j < prvky.length ; j++){
System.out.print(" "+matSousednostiOrig[i][j]);
}
System.out.println("");
}				}

int[] sousedi(int vstup){										//slouzi pro for v ohodnoceni
//	System.out.println("sousedi");
int array [] = null;
int pocitadlo = 0;
//System.out.println(matSousednosti[vstup].length);
for(int i = 0 ; i<matSousednosti[vstup].length ; i++){
//System.out.println("for");
//System.out.println(" "+matSousednosti[vstup][i]);
if(matSousednosti[vstup][i]== 1){
//System.out.println("true");
pocitadlo++;
}			}
//System.out.println("pocitadlo "+pocitadlo);
int j = 0;
array = new int [pocitadlo];
for(int k = 0 ; k<matSousednosti[vstup].length ; k++){
if(matSousednosti[vstup][k]==1){
array[j] = k;
j++;
}
}
//	System.out.println("vstup: "+vstup+",  array "+Arrays.toString(array));
return array;
}

void prohledDoHloubky (int s){
pocetSubGrafu=1;
doHloubky(s);

for(int i = 0 ; i < prvky.length ; i++){
if(prvky[i].color == "White"){
doHloubky(i);
pocetSubGrafu++;
}
}
}

void doHloubky (int s) { 									//vytvori predchudce apod.
int v;
prvky[s].color = "Gray";
//prvky[s].vzdalenost = 0;
cas++;
prvky[s].objeven = cas;
int array [] = sousedi(s);
for (int i = 0 ; i < array.length ; i++) {
v = array[i];
if (prvky[v].color == "White") {
prvky[v].predchudce = s;
doHloubky(v);
} 			}
prvky[s].color = "Black";
prvky[s].dokoncen = cas = cas+1;

}
void odeberSpoj(String spoj){
int index=0;
for(int i = 0 ; i< uzly.length ; i++){
if(uzly[i].equals(spoj)){
index = i;
break;
}
}
for(int i = 0 ; i < prvky.length ; i++){
for(int j = 0 ; j < prvky.length ; j++){
if(i==index || j==index){
matSousednosti[i][j]=0;
matSousednosti[j][i]=0;

}				}
}		}
void prebileni(){
for(int i = 0 ; i < prvky.length ; i++){
prvky[i].color = "White";
}
}
void origMatice(){

for(int i = 0 ; i < prvky.length ; i++){
for(int j = 0 ; j < prvky.length ; j++){
matSousednosti[i][j]=matSousednostiOrig[i][j];
matSousednosti[j][i]=matSousednostiOrig[j][i];
}
}
}
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10199 - Tourist Guide

Don't print a blank line at the start of the output.
Check input and AC output for thousands of problems on uDebug!

mehrab2603
New poster
Posts: 9
Joined: Sun Mar 30, 2014 6:56 pm

Re: 10199 - Tourist Guide

I'm using DFS to find articulation points, but getting TLE. Please help!

Code: Select all

``````#include <bits/stdc++.h>
#define MAX 101

using namespace std;
map<string, int> mymap;
vector<int> adj[MAX];
vector<int> apoints;
int col[MAX], par[MAX], low[MAX], dis[MAX], fin[MAX], tim, n;
void dfs();
void dfs_visit(int);
int source;

int main()
{
//freopen("output.txt", "w", stdout);
int caseno = 0;
bool start = false;
while(scanf("%d", &n) && n)
{
if(start == false) start = true;
else cout << endl;
int assig = 0;
string places[100];
for(int i = 0; i < n; i++)
{
string s1;
cin >> s1;
if(mymap.find(s1) == mymap.end())
{
mymap[s1] = assig;
places[assig] = s1;
assig++;
}
}
int r;
scanf("%d", &r);
for(int i = 0; i < r; i++)
{
string s1, s2;
cin >> s1 >> s2;
int u = mymap[s1];
int v = mymap[s2];
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs();
vector<string> output;
for(int i = 0; i < (int)apoints.size(); i++)
output.push_back(places[apoints[i]]);
sort(output.begin(), output.end());
printf("City map #%d: %d camera(s) found\n", ++caseno, output.size());
for(int i = 0; i < (int)output.size(); i++)
cout << output[i] << endl;
mymap.clear();
apoints.clear();
for(int i = 0; i < n; i++)
adj[i].clear();
}
return 0;
}

void dfs()
{
memset(low, 63, sizeof(low));
memset(col, 0, sizeof(col));
memset(par, -1, sizeof(par));
memset(dis, 63, sizeof(dis));
tim = 0;
for(int i = 0; i < n; i++)
{
if(col[i] == 0)
{
source = i;
dfs_visit(i);
if(adj[source].size() > 1)
{
int temp = fin[adj[source][0]];
for(int j = 1 ; j < (int)adj[source].size(); j++)
{
if(dis[adj[source][j]] > temp)
{
apoints.push_back(source);
break;
}
}
}
}
}
}

void dfs_visit(int u)
{
dis[u] = ++tim;
col[u] = 1;
low[u] = dis[u];
bool flag = false;
for(int i = 0; i < (int)adj[u].size(); i++)
{
int v = adj[u][i];
par[v] = u;
if(col[v] == 1)
low[u] = min(low[u], dis[v]);
else
{
if(par[u] == v) continue;
dfs_visit(v);
low[u] = min(low[u], low[v]);
}
if(low[v] >= dis[u] && u != source && !flag)
{
apoints.push_back(u);
flag = true;
}
}
col[u] = 2;
fin[u] = ++tim;
}
``````
Last edited by mehrab2603 on Tue Apr 01, 2014 7:43 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10199 - Tourist Guide

What are you trying to do on lines 75-77? Can you think of a faster way?
Check input and AC output for thousands of problems on uDebug!

mehrab2603
New poster
Posts: 9
Joined: Sun Mar 30, 2014 6:56 pm

Re: 10199 - Tourist Guide

Trying to determine if the source node is an articulation point or not. If the finishing time of the first adjacent node of the source node is less than the discovery time of any of the the next adjacent nodes, it is an articulation point.
Don't know how I can achieve this faster in this way, have to think differently I guess.

mehrab2603
New poster
Posts: 9
Joined: Sun Mar 30, 2014 6:56 pm

Re: 10199 - Tourist Guide

Ok I got rid of those loops, and used another array which keeps track of how many time dfs has been called from a node. If dfs has been called more than 1 time from a source node, then the node is an articulation point. Found some other errors that were causing TLE and fixed them. Now getting WA.

Code: Select all

``code removed after AC :)``

ree975
New poster
Posts: 5
Joined: Sat Sep 14, 2013 11:32 am

Re: 10199 - Tourist Guide

Is there anyone could help me? I passed all the test case in this discussion thread but still get WA.
I used "map" to achieve alphabetical order and cin.peek() to know whether to cout endl or not.

Code: Select all

``````Removed after AC, I made some mistake in implementing tarjan algo.
Thanks brianfry!
``````
Last edited by ree975 on Sat Feb 07, 2015 4:39 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10199 - Tourist Guide

Check input and AC output for thousands of problems on uDebug!

prashantharshi
New poster
Posts: 22
Joined: Wed May 21, 2014 10:16 am

Re: 10199 - Tourist Guide

i am stil getting WA even after considering graph as disconnected
here is my code

Code: Select all

``````#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <sstream>
#include <map>
#include <vector>
#define max 110

using namespace std;
map<string,int> mp;
vector<int> adj[max];
int disc[max];
int parent[max];
int status[max];
int arr[max];
int low[max];
int root,tme,n,counter;
string s;

void reset()
{
for(int i=0;i<max;i++)
{
adj[i].clear();
}
mp.clear();
memset(arr,0,sizeof(arr));
memset(status,0,sizeof(status));
memset(low,0,sizeof(low));
memset(disc,0,sizeof(disc));
memset(parent,-1,sizeof(parent));
tme=counter=0;
}

int dfs(int v)
{
disc[v]=++tme;
low[v]=disc[v];
status[v]=1;
int child=0;
for(int i=0;i<adj[v].size();i++)
{
int u=adj[v][i];
if(!status[u])
{
child++;
parent[u]=v;
low[u]=dfs(u);
low[v]=min(low[v],low[u]);
if(low[u]>=disc[v]&&v!=root)
{
arr[v]=1;
}
}
if(parent[v]!=u&&status[u])
{
low[v]=min(low[v],disc[u]);
}
}
if(v==root&&child>=2)
arr[v]=1;
return low[v];
}
int main(int argc, char const *argv[])
{
int t=1;
while(cin>>n)
{
if(n==0)
break;
reset();
for(int i=0;i<n;i++)
{
cin>>s;
if(!mp.count(s))
mp[s]=counter++;
}
cin>>n;
string s1,s2;
for(int i=0;i<n;i++)
{
cin>>s1>>s2;
adj[mp[s1]].push_back(mp[s2]);
adj[mp[s2]].push_back(mp[s1]);
}
for(int i=0;i<counter;i++)
{
if(!status[i])
{
root=i;
int k=dfs(i);
}
}
int count=0;
for(int i=0;i<max;i++)
{
if(arr[i])
count++;
}
cout<<"City map #"<<t<<": "<<count<<" camera(s) found"<<"\n";
t++;
std::vector<string> v;
for(int i=0;i<max;i++)
{
if(arr[i])
{
for(map<string,int>::iterator it=mp.begin();it!=mp.end();++it)
{
if(it->second==i)
v.push_back(it->first);
}
}
}
sort(v.begin(),v.end());
for(vector<string>::iterator it=v.begin();it<v.end();it++)
{
cout<<*it<<"\n";
}
cout<<"\n";
v.clear();
}
return 0;
}``````
Last edited by brianfry713 on Wed Apr 08, 2015 11:40 pm, edited 1 time in total.
Reason: Added code block