Cod sursa(job #1359305)

Utilizator stefan.vascoVanea Stefan Vascocenco stefan.vasco Data 24 februarie 2015 22:02:41
Problema Sortare topologica Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 4.73 kb
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.StringTokenizer;

class InputReader {

    private FileInputStream fs;
    private BufferedReader br;
    private StringTokenizer st;
    private final String delim;

    public InputReader(String fileName, String delim) {
        this.delim = delim;
        try {
            fs = new FileInputStream(fileName);
            br = new BufferedReader(new InputStreamReader(fs));
        } catch (FileNotFoundException ex) {
            ex.printStackTrace();
        }
    }

    public void closeReader() {
        try {
            br.close();
            fs.close();
        } catch (IOException ex) {
            ex.printStackTrace();
        }

    }

    public String nextString() {
        while (st == null || !st.hasMoreElements()) {
            String line = null;
            try {
                line = br.readLine();
                if (line != null && !line.isEmpty()) {
                    st = new StringTokenizer(line);
                } else {
                    return null;
                }
            } catch (IOException ex) {
                ex.printStackTrace();
            }
            return st.nextToken();
        }
        return st.nextToken(delim);
    }

    public byte nextByte() {
        return Byte.parseByte(nextString());
    }

    public short nextShort() {
        return Short.parseShort(nextString());
    }

    public int nextInt() {
        return Integer.parseInt(nextString());
    }

    public long nextLong() {
        return Long.parseLong(nextString());
    }

}

class Vertex {

    public int value;
    public LinkedList<Integer> inEdges;
    public LinkedList<Integer> outEdges;

    public Vertex(int vertexValue) {
        value = vertexValue;
        inEdges = new LinkedList<Integer>();
        outEdges = new LinkedList<Integer>();
    }
}

public class Main {

    private static HashMap<Integer, Vertex> graph;

    private static void readGraph() {
        InputReader ir = new InputReader("sortaret.in", " ");
        int vertexCount = ir.nextInt();
        int edgeCount = ir.nextInt();

        for (; edgeCount > 0; edgeCount--) {
            int nodeOut = ir.nextInt();
            int nodeIn = ir.nextInt();
            if (!graph.containsKey(nodeIn)) {
                Vertex newVertex = new Vertex(nodeIn);
                newVertex.inEdges.add(nodeOut);
                graph.put(nodeIn, newVertex);
            } else {
                graph.get(nodeIn).inEdges.add(nodeOut);
            }

            if (!graph.containsKey(nodeOut)) {
                Vertex newVertex = new Vertex(nodeOut);
                newVertex.outEdges.add(nodeIn);
                graph.put(nodeOut, newVertex);
            } else {
                graph.get(nodeOut).outEdges.add(nodeIn);
            }
        }
        ir.closeReader();
    }

    public static LinkedList<Integer> sortp() {
        LinkedList<Integer> sortedList = new LinkedList<Integer>();
        LinkedList<Vertex> initialList = new LinkedList<Vertex>();
        Iterator it = graph.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<Integer, Vertex> entry = (Map.Entry<Integer, Vertex>) it.next();
            Vertex currentVertex = entry.getValue();
            if (currentVertex.inEdges.size() == 0) {
                initialList.add(currentVertex);
            }
        }

        while (initialList.size() > 0) {
            Iterator listit = initialList.iterator();
            Vertex popVertex = (Vertex) listit.next();
            listit.remove();
            sortedList.add(popVertex.value);

            for (int vertexIndex : popVertex.outEdges) {
                Vertex outVertex = graph.get(vertexIndex);
                if (outVertex.inEdges.size() == 1) {
                    initialList.add(outVertex);
                }
            }
        }

        return sortedList;
    }

    private static void writeOutput(LinkedList<Integer> topsort) {
        try {
            PrintWriter pr = new PrintWriter("sortaret.out");
            for (int vertex : topsort) {
                pr.write(vertex + " ");
            }
            pr.close();

        } catch (FileNotFoundException ex) {
            ex.printStackTrace();
        }

    }

    public static void main(String[] args) {
        graph = new HashMap<Integer, Vertex>();
        readGraph();
        writeOutput(sortp());
    }

}