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

Post by uirapuru » Mon Jul 09, 2012 7:52 pm

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: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10199 - Tourist Guide

Post by Mukit Chowdhury » Thu Nov 15, 2012 10:29 pm

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

Post by hami » Fri Apr 26, 2013 9:52 am

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

Post by brianfry713 » Sat Apr 27, 2013 2:53 am

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

Post by hami » Sat Apr 27, 2013 1:41 pm

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

Post by brianfry713 » Fri May 17, 2013 1:32 am

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

Post by mehrab2603 » Sun Mar 30, 2014 6:58 pm

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

Post by brianfry713 » Mon Mar 31, 2014 10:51 pm

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

Post by mehrab2603 » Tue Apr 01, 2014 3:22 am

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

Post by mehrab2603 » Tue Apr 01, 2014 6:45 am

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

Post by ree975 » Fri Feb 06, 2015 2:09 pm

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

Post by brianfry713 » Sat Feb 07, 2015 12:36 am

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

Post by prashantharshi » Thu Apr 02, 2015 3:43 pm

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

Post Reply

Return to “Volume 101 (10100-10199)”