Untitled

mail@pastecode.io avatar
unknown
java
a year ago
4.8 kB
3
Indexable
Never
package z2;

import java.util.*;

public class Z2Drugie {
    public static void main(){
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int e = scanner.nextInt();

        int time = 0;
        ArrayList<Integer> nodeNumbers = new ArrayList<>();
        for(int i = 0; i < n; i++){
            time += scanner.nextInt();
            nodeNumbers.add(i+1);
        }

        Map<Integer, Node> setUpMap = new HashMap<>();
        PriorityQueue<Node> nodes = new PriorityQueue<>();
        for(Integer i = 0; i < e; i++){
            Integer prev = scanner.nextInt();
            Integer next = scanner.nextInt();

            int prevIndex = nodeNumbers.indexOf(prev);
            int nextIndex = nodeNumbers.indexOf(next);

            if (prevIndex != -1){
                nodeNumbers.remove(prevIndex);
            }
            if (nextIndex != -1){
                nodeNumbers.remove(nextIndex);
            }

            if (!setUpMap.containsKey(prev)) {
                Node node = new Node();
                node.setId(prev);
                node.addNext(next);
                setUpMap.put(prev, node);
            } else {
                Node node = setUpMap.get(prev);
                ArrayList<Integer> nextNodes = node.getNext();
                if (!nextNodes.contains(next)){
                    node.addNext(next);
                }
            }

            if (!setUpMap.containsKey(next)){
                Node node = new Node();
                node.setId(next);
                node.addPrev(prev);
                setUpMap.put(next, node);
            } else {
                Node node = setUpMap.get(next);
                ArrayList<Integer> prevNodes = node.getPrev();
                if (!prevNodes.contains(prev)){
                    node.addPrev(prev);
                }
            }
        }

        for(int i = 0; i < nodeNumbers.size(); i++){
            if (nodeNumbers.get(i) != 0){
                Node node = new Node();
                node.setId(nodeNumbers.get(i));
                setUpMap.put(nodeNumbers.get(i), node);
            }
        }

        nodes = createQueue(setUpMap, n);

        while (!nodes.isEmpty()){
            Node node = nodes.poll();
            setUpMap.remove(node.id);
            ArrayList<Integer> nextNodes = node.getNext();

            for(Integer nodeNumber : nextNodes){
                Node fromMap = setUpMap.get(nodeNumber);
                ArrayList<Integer> prevNodes = fromMap.getPrev();

                int index = prevNodes.indexOf(node.id);
                if (index > -1){
                    prevNodes.remove(index);
                }

                fromMap.setPrev(prevNodes);
                setUpMap.put(fromMap.id, fromMap);
            }

            System.out.println(node.id);
            nodes = createQueue(setUpMap, n);
        }

        System.out.println(time);
    }

    public static PriorityQueue<Node> createQueue(Map<Integer, Node> hashMap, int e){
        PriorityQueue<Node> nodePriorityQueue = new PriorityQueue<>();
        for (int i = 1; i <= e; i++){
            if (hashMap.get(i) != null){
                nodePriorityQueue.offer(hashMap.get(i));
            }
        }
        return nodePriorityQueue;
    }
}

class Node implements Comparable<Node>{
    int id;
    ArrayList<Integer> prev = new ArrayList<>();
    ArrayList<Integer> next = new ArrayList<>();

    public Node(int id, ArrayList<Integer> prev, ArrayList<Integer> next) {
        this.id = id;
        this.prev = prev;
        this.next = next;
    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", prev=" + prev +
                ", next=" + next +
                '}';
    }

    @Override
    public int compareTo(Node other) {
        // sort based on the smallest t value
        int r = Integer.compare(this.prev.size(), other.prev.size());
        return r == 0 ? Integer.compare(this.id, other.id) : r;
    }

    public void addPrev(Integer prevInt){
        prev.add(prevInt);
    }

    public void addNext(Integer nextInt){
        next.add(nextInt);
    }
    public Node() {
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public ArrayList<Integer> getPrev() {
        return prev;
    }

    public void setPrev(ArrayList<Integer> prev) {
        this.prev = prev;
    }

    public ArrayList<Integer> getNext() {
        return next;
    }

    public void setNext(ArrayList<Integer> next) {
        this.next = next;
    }
}