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 .
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:
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:
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;
}
}