Úloha 1

Make

Zadání

Limit: 15s

Jak na to:

• vytvořit z cílů a podcílů graf
• projít graf do hloubky a pro každý uzel si pamatuji stav (FRESH, OPEN, CLOSED)
• pokud při procházení narazím na OPEN uzel, vypsat chybu
• pokud při procházení narazím na CLOSED uzel, nevypisovat příkazy (vznikla by duplicita)
• rychlejší by měla být nerekurzivní varianta, ale dá se to v Javě stihnout i s rekurzí

Jedná se v podstatě o topologické uspořádání grafu.

package pal;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in, "cp1250"));
        HashMap<String, Uloha> ulohy = new HashMap<String, Uloha>();
        Uloha uloha = null;
        boolean zacatek = true;
        Uloha prvni = null;
 
        String vz = br.readLine();
 
        while (vz != null) {
            if (vz.charAt(0) == '\t') {
                uloha.prikazy.append(vz.substring(1));
                uloha.prikazy.append("\n");
            } else {
                StringTokenizer st = new StringTokenizer(vz, " :");
                String nazev = st.nextToken();
                if (ulohy.containsKey(nazev)) {
                    uloha = ulohy.get(nazev);
                } else {
                    uloha = new Uloha();
                    if (zacatek) {
                        prvni = uloha;
                        zacatek = false;
                    }
                    ulohy.put(nazev, uloha);
                }
                while (st.hasMoreTokens()) {
                    nazev = st.nextToken();
                    if (!ulohy.containsKey(nazev)) {
                        ulohy.put(nazev, new Uloha());
                    }
                    uloha.pridej(ulohy.get(nazev));
                }
            }
            vz = br.readLine();
        }
        StringBuilder out = new StringBuilder();
        prvni.vypis(out);
        System.out.print(out);
    }
}
 
class Uloha {
    boolean vypsana = false;
    boolean navstivena = false;
    List<Uloha> podulohy = new ArrayList<Uloha>();
    StringBuilder prikazy = new StringBuilder();
 
    void pridej(Uloha poduloha) {
        podulohy.add(poduloha);
    }
 
    void vypis(StringBuilder out) {
        if (!vypsana) {
            if (navstivena) {
                System.out.println("ERROR");
                System.exit(0);
            }
            navstivena = true;
            for (Uloha uloha : podulohy) {
                uloha.vypis(out);
            }
            out.append(prikazy);
            vypsana = true;
        }
    }
}