Nepostradatelný most

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

Java

/**
 * 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;
    }
}

Řešení

Příklad

Vstup

Výstup

Kód

Doporučujeme