Cod sursa(job #1430599)

Utilizator BFlorin93Balint Florin-Lorand BFlorin93 Data 8 mai 2015 17:32:01
Problema Sortare topologica Scor 20
Compilator java Status done
Runda Arhiva educationala Marime 2.43 kb
import java.io.*;
import java.util.*;

/**
 * Created by intern on 5/8/15.
 */
public class Main {
    private List<Integer>[] neighbours;
    private PrintWriter printWriter;
    private static String outTxt = "sortaret.out";
    public Main(List<Integer>[] neighbours)
    {
        try {
            printWriter = new PrintWriter(outTxt, "UTF-8");
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        }

        this.neighbours = neighbours;
    }

    public static void main(String[] args) throws IOException {
        FileReader in = null;
        String line = null;
        int n = 0;
        int m = 0;
        try {
            in = new FileReader("sortaret.in");
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        BufferedReader br = new BufferedReader(in);

        line = br.readLine();
        Scanner scanner = new Scanner(line);
        n = scanner.nextInt();
        m = scanner.nextInt();
        List<Integer>[] neighbours = new List[n];
        for (int  i = 0;i < n;i++)
        {
            neighbours[i] = new ArrayList<>();
        }

        int edgeFrom,edgeTo;

        for (int i = 0;i < m; i++)
        {
            line = br.readLine();
            scanner = new Scanner(line);

            edgeFrom = scanner.nextInt();
            edgeTo = scanner.nextInt();
            neighbours[edgeFrom - 1].add(edgeTo - 1);
        }
        for (int i = 0;i< n;i++)
            System.out.println(neighbours[i]);

        br.close();
        Main topoSort = new Main(neighbours);
        topoSort.dfs();
    }



    public void dfs()
    {
        int  n = neighbours.length;
        boolean[] visited = new boolean[n];
        for (int i = 0;i<n;i++)
            visited[i] = false;

        Deque<Integer> integers = new ArrayDeque<>();

        for (int i = 0;i < n;i++)
        {
            if (!visited[i]) dfsComponent(i,visited,integers);
        }

        for (Integer i : integers)
         printWriter.print(i + 1 + " ");

        printWriter.close();
    }

    private void dfsComponent(int i,boolean[] visited,Deque<Integer> queue) {
        visited[i] = true;

        for (Integer neighbour : neighbours[i])
        {
            if(!visited[neighbour])
            {
                dfsComponent(neighbour,visited,queue);
            }
        }

        queue.addFirst(i);
    }


}