Nepostradatelný most
Nepostradatelný most mezi uzly 3 a 4
Nepostradatelný most mezi uzly 3 a 4

Hledání nepostradatelných mostů je častou úlohou teorie grafů, jejímž cílem je nalézt takové hrany, po jejichž odebrání by se daný neorientovaný graf rozpadl na více částí. Pokud tuto úlohu přeformulujeme, tak hledáme takové hrany, které nejsou součástí žádného cyklu (ke všem uzlům uvnitř cyklu vede přinejmenším jedna další alternativní cesta).

Řešení

Řešením této úlohy je prohledávání do hloubky rozšířené o některé aspekty Tarjanova algoritmu. Pokud při prohledávání grafu narazíme na zpětnou hranu vedoucí do uzlu U, pak všechny stromové hrany průchodu až do návratu do uzlu U jsou uvnitř cyklu. Pokud objevíme příčnou hranu, pak nemusíme činit nic, protože se jedná o již zpracovaný případ zpětné hrany (objevený z opačné strany).

Za předpokladu, že uzel leží ve více cyklech, musíme rozhodnout, který cyklus je nejdelší (ve smyslu návratu z rekurze). Což je zřejmě ten, jehož cílovým uzlem je uzel, který byl objeven nejdříve (je ve stromu průchodu nejvýše).

Složitost tohoto řešení je totožná se složitostí prohledávání do hloubky, čili O(\\vert U \\vert + \\vert H \\vert).


Příklad

Nalezněte nepostradatelné mosty. Vstupní data budou programu předána na standardním vstupu. Výstup bude realizován pomocí standardního výstupu.

Vstup

Prvním řádkem vstupu je počet uzlů grafu, na dalších řádcích se vyskytují dvojice oddělené mezerou reprezentující hrany (počáteční uzel, koncový uzel). Vstup je ukončen dvojicí „0 0“.

Vzor:

8
0 3
1 3
2 3
4 5
4 6
4 7
3 4
0 1
1 2
5 6
6 7
0 0

Výstup

Výstupem algoritmu jsou dvojice uzlů oddělené mezerou reprezentující nepostradatelnou hranu grafu (nepostradatelný most), na pořadí uzlů nezáleží. Výstup je ukončen dvojicí „0 0“.

Vzor:

3 4
0 0

Kód

 /**
  * Resi problem nepostradatelneho mostu
  * @author Pavel Micka
  */
 public class Main {
     /**
      * Vystupni buffer
      */
     private static StringBuilder builder = new StringBuilder(4096);
     /**
      * Citac
      */
     private static int counter = 0;
 
     /**
      * @param args the command line arguments
      */
     public static void main(String[] args) throws IOException {
         BufferedReader r = new BufferedReader(new InputStreamReader(System.in), 2048);
 
         int nodeCount = Integer.valueOf(r.readLine());
         Node[] nodes = new Node[nodeCount];
 
         if (nodeCount == 0){
             System.out.println("0 0");
             return;
         } //zadny uzel - zadny problem
 
         for (int i = 0; i < nodes.length; i++) {
             nodes[i] = new Node(i);
         }
 
         readInput(r, nodes);
 
         nodes[0].setState(Node.OPEN);
         solve(nodes[0], null);
         nodes[0].setState(Node.CLOSED);
         
         builder.append("0 0"); //uzavri vstup
 
         System.out.println(builder.toString()); //vystup
     }
 
     /**
      * Precte vstupni data
      * @param r vstupni stream
      * @param nodes pole uzlu
      * @throws IOException v pripade, ze nelze ze streamu cist
      * @throws NumberFormatException v pripade nevalidnich dat (spane reprezentace cisel) ve streamu
      */
     private static void readInput(BufferedReader r, Node[] nodes) throws IOException, NumberFormatException {
         String line = null;
         while ((line = r.readLine()) != null) {
             StringTokenizer tokenizer = new StringTokenizer(line, " ");
             int parent = Integer.valueOf(tokenizer.nextToken());
             int child = Integer.valueOf(tokenizer.nextToken());
             nodes[child].getNeighbours().add(nodes[parent]);
             nodes[parent].getNeighbours().add(nodes[child]);
         }
     }
 
     /**
      * Resi pruchodem do hloubky problem nepostradelnych mostu
      * @param node zpracovavany uzel
      * @param parent rodic tohoto uzlu
      * @return cislo nejvyse dosazitelneho uzlu cyklem, Integer.MAX_VALUE v pripade,
      * ze takovy uzel neexistuje
      */
     private static int solve(Node node, Node parent) {
         node.setDiscovered(counter++);
         int cycleTo = Integer.MAX_VALUE; //cyklus neexistuje
         for (Node n : node.getNeighbours()) { //pro vsechny sousedy
             if (!n.equals(parent)) { //kteri nejsou rodicem uzlu
                 if (n.getState() == Node.FRESH) { //a jsou cerstvi
                     n.setState(Node.OPEN); //otevri je
                     int childCycleTo = solve(n, node); //zjisti nejvyssi uzel, na lze ktery dosahnout
                     if (childCycleTo < cycleTo && childCycleTo != node.getDiscovered()) { //pokud to neni tento uzel a nedosahneme jiz na vyssi
                         cycleTo = childCycleTo; //pak jsme objevili nejvyssi dosazitelny uzel
                     } else if (childCycleTo == Integer.MAX_VALUE) { //pokud cyklus z ditete neexistuje
                         builder.append(node.getId() + " " + n.getId() + "\\n"); //pak je tento most nepostradatelny
                     }
                 } else if (n.getState() == Node.OPEN) { //pokud je uzel otevreny
                     cycleTo = n.getDiscovered(); //objevili jsme zpetnou hranu (cyklus)
                 }
             }
         }
         node.setState(Node.CLOSED); //uzavri uzel
         return cycleTo; //vrat nejvyssi dosazitelny uzel
     }
 }
 
 /**
  * Uzel grafu
  * @author Pavel Micka
  */
 class Node {
     private int discovered; //identifikator uzlu
     private int id;//identifikator uzlu
     public static final int FRESH = 0; //cerstvy uzel
     public static final int OPEN = 1; //otevreny uzel
     public static final int CLOSED = 2; //uzavreny uzel
     private List<Node> neighbours; //sousede uzlu
     private int state; //sousede uzlu
 
     public Node(int id) {
         neighbours = new ArrayList<Node>();
         this.id = id;
         state = FRESH;
     }
 
     /**
      * @return the discovered
      */
     public int getDiscovered() {
         return discovered;
     }
 
     /**
      * @param discovered the discovered to set
      */
     public void setDiscovered(int discovered) {
         this.discovered = discovered;
     }
 
     /**
      * @return the id
      */
     public int getId() {
         return id;
     }
 
     /**
      * @param id the id to set
      */
     public void setId(int id) {
         this.id = id;
     }
 
     /**
      * @return the neighbours
      */
     public List<Node> getNeighbours() {
         return neighbours;
     }
 
     /**
      * @param neighbours the neighbours to set
      */
     public void setNeighbours(List<Node> neighbours) {
         this.neighbours = neighbours;
     }
 
     /**
      * @return the state
      */
     public int getState() {
         return state;
     }
 
     /**
      * @param state the state to set
      */
     public void setState(int state) {
         this.state = state;
     }
 }
 
 







Doporučujeme