fork download
copy 
  1.  
  2. import java.io.BufferedReader;
  3. import java.io.IOException;
  4. import java.io.InputStreamReader;
  5. import java.io.PrintStream;
  6. //import java.util.Scanner;
  7.  
  8. import java.util.Arrays;
  9.  
  10.  
  11. //City map #1: 1 camera(s) found
  12.  
  13. public class Main {
  14.  
  15.    //private static Scanner sc = new Scanner(System.in);
  16.    private static BufferedReader bfr;
  17.    private static PrintStream bwr;
  18.    static int pocetSpoju =1;
  19.    static DfsMatice base;
  20.    static int pocetSub;
  21.    static String vystup = "";
  22.    static int pocitadloMest=0;
  23.    static int pocitadloKrizovatek=0;
  24.    static String localVystup="";
  25.  
  26.    static void zpracovani(int pocetMest) throws IOException {
  27.       pocitadloMest++;
  28.        pocitadloKrizovatek=0;
  29.       localVystup="";
  30.          String vstup = new String();         
  31.             for(int i = 0 ; i < pocetMest  ; i++){               
  32.             vstup = vstup + bfr.readLine().trim()+" ";
  33.             }
  34.             //vstup = vstup + bfr.readLine().trim();
  35.          //   System.out.println(vstup.trim());
  36.             String [] poleVstupu = vstup.trim().split(" ");
  37.             Arrays.sort(poleVstupu);
  38.             base.vytvoreniUzlu(poleVstupu);
  39.             pocetSpoju = Integer.valueOf(bfr.readLine().trim());
  40.          //   System.out.println("pocetSpoju"+pocetSpoju);
  41.             //bfr.readLine();
  42.             for(int i = 0 ; i<pocetSpoju ; i++){
  43.                base.vytvoreniSpojeMaticeObousmerna(bfr.readLine().trim());         
  44.             }      
  45.             base.vytvoreniOrigMtice();
  46.          //   base.vypisMaticeorig();
  47.          //base.vypisMatice();   
  48.          base.prohledDoHloubky(0);      
  49.          pocetSub =base.pocetSubGrafu;
  50.          //System.out.println(pocetSub);
  51.          base.prebileni();
  52.          for(int i = 0 ; i<poleVstupu.length ; i++){
  53.          vyhodnoceni(poleVstupu[i]);
  54.          }
  55.          vystup = vystup+"City map #"+pocitadloMest+": "+pocitadloKrizovatek+" camera(s) found"+"\n"+localVystup+"\n";
  56.    }   
  57.    static void vyhodnoceni(String vyhod) {
  58.       base.odeberSpoj(vyhod);
  59.       base.prohledDoHloubky(0);   
  60.       //base.vypisMatice();      
  61.       //base.vypisMaticeorig();
  62.       ////System.out.println(base.pocetSubGrafu);
  63.    //   System.out.println("base.pocetSubGrafu "+base.pocetSubGrafu+" "+"pocetSub "+pocetSub);
  64.       if(base.pocetSubGrafu>(pocetSub+1)){
  65.          localVystup = localVystup+vyhod+"\n";
  66.          pocitadloKrizovatek++;
  67.       }
  68.       base.prebileni();
  69.       base.origMatice();
  70.    }
  71.    public static void main(String[] args) throws NumberFormatException, IOException {
  72.       bfr = new BufferedReader(new InputStreamReader(System.in));
  73.       bwr = new PrintStream(System.out);
  74.       bwr.print("line1\n");
  75.       base = new DfsMatice();
  76.       int pocet = 0;
  77.       while(true){
  78.          pocet = Integer.valueOf(bfr.readLine().trim());
  79.          //System.out.println("pocet"+pocet);
  80.          if(pocet!=0){
  81.       zpracovani(pocet);      }
  82.          else{
  83.             break;         }      }
  84.  
  85.    //   System.out.print(vystup.trim());
  86.       //System.out.print("\n"+vystup.trim());
  87.       bwr.print("\n"+vystup.trim());
  88.       }
  89. }
  90.  class Prvek {   
  91.    public String nazev;
  92.    public Hrana hrana;
  93.    //Prvek top;
  94.    public String color;
  95.    public int vzdalenost;
  96.    public int predchudce;
  97.    public int objeven;
  98.    public int dokoncen;   
  99.    Prvek(String nazev) {
  100.       this.nazev = nazev;
  101.       this.hrana = null;
  102.       this.color = "White";
  103.       this.vzdalenost = Integer.MAX_VALUE;
  104.       this.predchudce = -1;
  105.       this.objeven = Integer.MAX_VALUE;
  106.       this.dokoncen = Integer.MAX_VALUE;
  107.    }
  108.  
  109. }
  110. class Hrana {
  111.    public int vrchol;
  112.    public Hrana dalsi;
  113.  
  114.    public Hrana (int vrchol) {       
  115.       this.vrchol = vrchol;
  116.       dalsi = null;
  117.       } }
  118.  
  119.  
  120.  
  121.  
  122.  class DfsMatice {
  123.    private static String[] uzly;                  
  124.    private static int matSousednosti [][];            //matice souslednosti
  125.    private static int matSousednostiOrig [][];
  126.    public Prvek [] prvky;                        //pole objektu
  127.    public Prvek [] vystupni;      
  128. //   private Prvek prac;
  129.    private static int cas = 0;
  130.    int pocetSubGrafu;
  131.  
  132.  
  133.    DfsMatice() {
  134.       this.prvky=null;
  135.       this.pocetSubGrafu=1;
  136.    }      
  137.    void vytvoreniOrigMtice(){
  138.       matSousednostiOrig = new int [uzly.length][uzly.length];
  139.       for(int i = 0 ; i < prvky.length ; i++){
  140.          for(int j = 0 ; j < prvky.length ; j++){            
  141.          matSousednostiOrig[i][j]=matSousednosti[i][j];
  142.          matSousednostiOrig[j][i]=matSousednosti[j][i];            
  143.                   }         
  144.    }
  145.    }
  146.  
  147.    void vytvoreniUzlu(String[] pole){
  148.    uzly = pole;   
  149.    matSousednosti = new int [uzly.length][uzly.length];   
  150.    prvky = new Prvek [pole.length];
  151.    for(int i = 0 ; i < pole.length ; i++){
  152.       prvky[i] = new Prvek(pole[i]);      }      
  153.    Arrays.toString(pole);
  154.    }      
  155.    void vytvoreniSpojeMaticeObousmerna(String spoj) throws IOException {         //vytvari matici sousednosti
  156.       //System.out.println("vytvoreniSpojeMaticeObousmerna: "+spoj);
  157.       String [] casti = spoj.trim().split(" ");
  158.       if(casti.length>2){
  159.          throw new IOException();
  160.       }
  161.       for(int i = 0 ; i < prvky.length ; i++){
  162.          for(int j = 0 ; j < prvky.length ; j++){
  163.          if(prvky[i].nazev.equals(casti[0])&&prvky[j].nazev.equals(casti[1])){
  164.          matSousednosti[i][j]=1;
  165.          matSousednosti[j][i]=1;
  166.          return;
  167.       }            }      
  168.    }   }
  169.  
  170.    void vypisMatice() {                              //vypise matici sousednosti
  171.       System.out.println("");
  172.       System.out.println("Vypis matici:");
  173.       for(int i = 0 ; i < prvky.length ; i++){         
  174.          for(int j = 0 ; j < prvky.length ; j++){         
  175.          System.out.print(" "+matSousednosti[i][j]);               
  176.          }
  177.          System.out.println("");
  178.       }            }
  179.  
  180.    void vypisMaticeorig() {                              //vypise matici sousednosti
  181.       System.out.println("");
  182.       System.out.println("Vypis matici orig:");
  183.       for(int i = 0 ; i < prvky.length ; i++){         
  184.          for(int j = 0 ; j < prvky.length ; j++){         
  185.          System.out.print(" "+matSousednostiOrig[i][j]);               
  186.          }
  187.          System.out.println("");
  188.       }            }
  189.  
  190.    int[] sousedi(int vstup){                              //slouzi pro for v ohodnoceni
  191.    //   System.out.println("sousedi");
  192.       int array [] = null;
  193.       int pocitadlo = 0;
  194.       //System.out.println(matSousednosti[vstup].length);
  195.       for(int i = 0 ; i<matSousednosti[vstup].length ; i++){
  196.          //System.out.println("for");
  197.          //System.out.println(" "+matSousednosti[vstup][i]);
  198.          if(matSousednosti[vstup][i]== 1){
  199.             //System.out.println("true");
  200.          pocitadlo++;
  201.          }         }
  202.          //System.out.println("pocitadlo "+pocitadlo);
  203.          int j = 0;
  204.          array = new int [pocitadlo];
  205.       for(int k = 0 ; k<matSousednosti[vstup].length ; k++){
  206.          if(matSousednosti[vstup][k]==1){
  207.             array[j] = k;
  208.             j++;
  209.          }
  210.       }   
  211.    //   System.out.println("vstup: "+vstup+",  array "+Arrays.toString(array));
  212.       return array;
  213.    }
  214.  
  215.    void prohledDoHloubky (int s){
  216.       pocetSubGrafu=1;      
  217.       doHloubky(s);
  218.  
  219.       for(int i = 0 ; i < prvky.length ; i++){
  220.          if(prvky[i].color == "White"){
  221.             doHloubky(i);
  222.             pocetSubGrafu++;
  223.          }
  224.       }
  225.    }
  226.  
  227.  
  228.    void doHloubky (int s) {                            //vytvori predchudce apod.
  229.       int v;            
  230.       prvky[s].color = "Gray";
  231.       //prvky[s].vzdalenost = 0;
  232.       cas++;      
  233.       prvky[s].objeven = cas;
  234.       int array [] = sousedi(s);
  235.       for (int i = 0 ; i < array.length ; i++) {
  236.          v = array[i];
  237.       if (prvky[v].color == "White") {          
  238.          prvky[v].predchudce = s;
  239.          doHloubky(v);
  240.       }          }
  241.       prvky[s].color = "Black";
  242.       prvky[s].dokoncen = cas = cas+1;
  243.  
  244.       }          
  245.    void odeberSpoj(String spoj){
  246.       int index=0;
  247.       for(int i = 0 ; i< uzly.length ; i++){
  248.          if(uzly[i].equals(spoj)){
  249.             index = i;
  250.             break;
  251.          }
  252.       }
  253.       for(int i = 0 ; i < prvky.length ; i++){
  254.          for(int j = 0 ; j < prvky.length ; j++){
  255.          if(i==index || j==index){
  256.          matSousednosti[i][j]=0;
  257.          matSousednosti[j][i]=0;
  258.  
  259.       }            }      
  260.    }      }
  261.    void prebileni(){
  262.       for(int i = 0 ; i < prvky.length ; i++){
  263.          prvky[i].color = "White";
  264.       }
  265.    }
  266.    void origMatice(){         
  267.  
  268.          for(int i = 0 ; i < prvky.length ; i++){
  269.             for(int j = 0 ; j < prvky.length ; j++){               
  270.             matSousednosti[i][j]=matSousednostiOrig[i][j];
  271.             matSousednosti[j][i]=matSousednostiOrig[j][i];               
  272.                      }         
  273.       }
  274.    }
  275. }
Success #stdin #stdout 0.08s 380160KB
comments (?)
stdin
copy 
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
0
stdout
copy 
line1

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

City map #2: 1 camera(s) found
sambodromo
https://ideone.com/J1rdiv
language:
Java (HotSpot 12)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!