[ create a new paste ] login | about

Link: http://codepad.org/fLDdQjpt    [ raw code | fork ]

Plain Text, pasted on Jan 25:
import java.util.ArrayList;
import java.util.Scanner;


public class TopologicalOrdersWithOnePermutation {
    final ArrayList<ArrayList<Integer>> edgesFrom = new ArrayList<>();
    final int[] degreeTo;
    final int size;
    final int[] answer;

    public TopologicalOrdersWithOnePermutation(int size) { //O(n)
        degreeTo = new int[size];
        answer = new int[size];
        for (int i = 0; i < size; ++i) {
            edgesFrom.add(new ArrayList<>());
        }
        this.size = size;
    }

    public void addEdge(int from, int to) { //O(1)
        edgesFrom.get(from).add(to);
        ++degreeTo[to];
    }

    final ArrayList<Integer> myStack = new ArrayList<>();

    public void createAnswer() { //O(n+m)
        int pos = 0;
        int swapPlace = -1;
        for (int i = 0; i < size; ++i)
            if (degreeTo[i] == 0)
                myStack.add(i);

        while(pos<size) {
            if (myStack.isEmpty()) {
                System.out.println("graph with cycles" );
                return;
            }
            if (swapPlace == -1 && myStack.size() > 1) {
                int x = myStack.remove(myStack.size()-1);
                int y = myStack.remove(myStack.size()-1);
                removeVertice(x);
                removeVertice(y);
                swapPlace = pos;
                answer[pos++] = x;
                answer[pos++] = y;
                continue;
            }
            int x = myStack.remove(myStack.size()-1);
            removeVertice(x);
            answer[pos++] = x;

        }
        if (swapPlace == -1) {
            System.out.println("one order");
            for (int i = 0; i < size; ++i) System.out.print(answer[i] + " ");
            System.out.println();
        } else {
            System.out.println("first order");
            for (int i = 0; i < size; ++i) System.out.print(answer[i] + " ");
            System.out.println();
            int c = answer[swapPlace];
            answer[swapPlace] = answer[swapPlace + 1];
            answer[swapPlace + 1] = c;
            System.out.println("second order");
            for (int i = 0; i < size; ++i) System.out.print(answer[i] + " ");
            System.out.println();
        }
    }

    private void removeVertice(int from) { // O(m) at all calls
        for (int to : edgesFrom.get(from)) {
            if (--degreeTo[to] == 0) //One run for each edge
                myStack.add(to);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        TopologicalOrdersWithOnePermutation orders=  new TopologicalOrdersWithOnePermutation(n);
        int m = scanner.nextInt();
        for(int i = 0; i<m;++i){
            int from  = scanner.nextInt();
            int to = scanner.nextInt(); // numeration from 0
            orders.addEdge(from, to);
        }
        orders.createAnswer();
    }

}



Create a new paste based on this one


Comments: