Cod sursa(job #2443968)

Utilizator CiobaCatalinCioba Catalin CiobaCatalin Data 29 iulie 2019 22:03:24
Problema Sortare topologica Scor 50
Compilator java Status done
Runda Arhiva educationala Marime 4.81 kb
import java.io.*;
import java.util.*;

class Main {

    static void arrayTopSort(List<List<Integer>> adj, FileWriter fout) throws IOException {
        int[] inDegree = new int[adj.size()];
        Arrays.fill(inDegree, 0);
        
        for (int u = 0; u < adj.size(); u++) {
            for (int v : adj.get(u)) {
                inDegree[v]++;
            }
        }

        //for (int u = 0; u < adj.size(); u++) {
        //    if (inDegree[u] == 0) {

    }

    static void dfsTopSort(List<List<Integer>> adj, FileWriter fout) throws IOException {
        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[adj.size()];
        Arrays.fill(visited, false);

        for (int u = 0; u < adj.size(); u++) {
            if (!visited[u]) {
                dfs(u, adj, visited, stack);
            }
        }
        
        while (!stack.empty()) {
            int node = stack.pop();
            fout.write((node + 1) + " ");
        }
    }

    static void dfs(int node, List<List<Integer>> adj, boolean[] visited, Stack<Integer> stack) {
        visited[node] = true;

        for (int v: adj.get(node)) {
            if (!visited[v]) {
                dfs(v, adj, visited, stack);
            }
        }

        stack.push(node);
    }

    public static void main(String[] args) {
        try (FileWriter fout = new FileWriter(new File("sortaret.out"))) {
            Reader in = new Reader("sortaret.in");

            int V, E;
            V = in.nextInt();
            E = in.nextInt();

            List<List<Integer>> adj = new LinkedList<>();

            for (int i = 0; i < V; i++) {
                adj.add(new ArrayList<>());
            }

            int u, v;
            for (int i = 0; i < E; i++) {
                u = in.nextInt();
                v = in.nextInt();
                
                adj.get(u - 1).add(v - 1);
            }
    
            dfsTopSort(adj, fout);
        } catch (IOException ex) {
            ex.printStackTrace();
        }
    }

    static class Pair<K, V> {
        K key;
        V value;

        public Pair(K k, V v) {
            this.key = k;
            this.value = v;
        }
    }

    static class Reader
{
    final private int BUFFER_SIZE = 1 << 16;
    private DataInputStream din;
    private byte[] buffer;
    private int bufferPointer, bytesRead;

    public Reader()
    {
        din = new DataInputStream(System.in);
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
    }

    public Reader(String file_name) throws IOException
    {
        din = new DataInputStream(new FileInputStream(file_name));
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
    }

    public String readLine() throws IOException
    {
        byte[] buf = new byte[64]; // line length
        int cnt = 0, c;
        while ((c = read()) != -1)
        {
            if (c == '\n')
                break;
            buf[cnt++] = (byte) c;
        }
        return new String(buf, 0, cnt);
    }

    public int nextInt() throws IOException
    {
        int ret = 0;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();
        do
        {
            ret = ret * 10 + c - '0';
        }  while ((c = read()) >= '0' && c <= '9');

        if (neg)
            return -ret;
        return ret;
    }

    public long nextLong() throws IOException
    {
        long ret = 0;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();
        do {
            ret = ret * 10 + c - '0';
        }
        while ((c = read()) >= '0' && c <= '9');
        if (neg)
            return -ret;
        return ret;
    }

    public double nextDouble() throws IOException
    {
        double ret = 0, div = 1;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();

        do {
            ret = ret * 10 + c - '0';
        }
        while ((c = read()) >= '0' && c <= '9');

        if (c == '.')
        {
            while ((c = read()) >= '0' && c <= '9')
            {
                ret += (c - '0') / (div *= 10);
            }
        }

        if (neg)
            return -ret;
        return ret;
    }

    private void fillBuffer() throws IOException
    {
        bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
        if (bytesRead == -1)
            buffer[0] = -1;
    }

    private byte read() throws IOException
    {
        if (bufferPointer == bytesRead)
            fillBuffer();
        return buffer[bufferPointer++];
    }

    public void close() throws IOException
    {
        if (din == null)
            return;
        din.close();
    }
}
}