Cod sursa(job #1358402)

Utilizator stefan.vascoVanea Stefan Vascocenco stefan.vasco Data 24 februarie 2015 16:34:51
Problema Sortare topologica Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 4.2 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.LinkedList;
import java.util.List;
import java.util.StringTokenizer;
import java.util.logging.Level;
import java.util.logging.Logger;

class Vertex {

    LinkedList<Vertex> edges;
    int vertex;
    boolean visited;

    public Vertex(int indexVertex) {
        vertex = indexVertex;
        edges = new LinkedList<Vertex>();
    }

    public void adaugaMuchie(short indexVertex) {
        edges.add(new Vertex(indexVertex));
    }

    public LinkedList<Vertex> getEdges() {
        return this.edges;
    }

    public int getIndex() {
        return this.vertex;
    }
}

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());
    }

}

public class Main {

    private static boolean addVertex(Vertex currentNode, int parentIndex, int newNodeIndex) {
        if (currentNode.vertex == parentIndex) {
            currentNode.edges.add(new Vertex(newNodeIndex));
            return true;
        } else {
            for (Vertex ver : currentNode.edges) {
                if (addVertex(ver, parentIndex, newNodeIndex)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void DFS(Vertex currentNode, List<Integer> topsort) {
        for (Vertex ver : currentNode.edges) {
            if (!topsort.contains(ver.vertex)) {
                DFS(ver, topsort);
            }
        }
        topsort.add(currentNode.vertex);
    }

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

        for (int edgeIndex = 1; edgeIndex < edgeCount; edgeIndex++) {
            addVertex(parentNode, ir.nextInt(), ir.nextInt());
        }
        ir.closeReader();
        return parentNode;
    }

    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) {
        Vertex parentNode = readGraph();
        LinkedList<Integer> topsort = new LinkedList<Integer>();
        DFS(parentNode, topsort);
        writeOutput(topsort);
    }

}