контрольная №2

//1
 Value delete(Key key) {
        если root null
                вернуть null;
        node prev := root;
        node current := prev;
        пока current.key <> key || current = null
                если key < current.key
                    prev := current;
                    current := current.left;
                если key > current.key
                    prev := current;
                    current := current.right;

        если current.key = key
             проверяем не лист ли он
                 если лист, просто удаляем
                 обновляем указатель у предыдущего на текущий, что он null
             иначе если у него есть правые потомки
                  доходим до минимального правого(один раз вправо и далее влево до упора)
                  меняем местами текущий и минимальный, удаляем минимальный, предварительно сохранив значение
                  обновляем указатель у предыдущего на текущий
                  вернуть value
             иначе
                   доходим до максимального левого
                   меняем местами текущий и максимальный и удаляем его, сохранив в переменную
                   обновляем указатель у предыдущего на текущий
                   вернуть value
        если не нашли key
                вернуть null
    }


//2
   Node rotateLeft(Node y) {
        Node x = y.right;
        y.right = x.left;
        x.left = y;
        fixHeight(y);
        fixHeight(x);
        return x;
    }



//3
    void rehash() {
        if (loadFactor() > loadFactor) {
            int oldM = m;
            List<Key, Value>[] prevTable = hashTable;
            n = 0;
            m *= 2;
            hashTable = new List[m];
            for (int i = 0; i < m; ++i) {
                hashTable[i] = new List<>();
            }
            for (int i = 0; i < oldM; ++i) {
                if (prevTable[i] != null) {
                    Node<Key, Value> temp = prevTable[i].head;
                    while (temp != null) {
                        this.put(temp.key, temp.value);
                        temp = temp.next;
                    }
                }
            }
        }
    }

    void put(Key key, Value value) {
        if(loadFactor > 0.75)
                rehash();
        int hash = hashCode(key);
        int index = index(hash);
        hashTable[index].add(key, value);
    }

    void add (Key key, Value value) {
        if (head == null) {
            head = new Node<>(key, value, null);
            return;
        } else if (head.next == null) {
            if (head.key.equals(key)) {
                head.value = value;
                return;
            } else {
                head.next = new Node<>(key, value, null);
                return;
            }
        } else {
            Node temp = head;
            while (temp != null) {
                if (temp.key.equals(key)) {
                    temp.value = value;
                    return;
                }
                temp = temp.next;
            }

            temp = head;
            head = new Node<>(key, value, temp);
            return;
        }
    }




//4
    void haveCycle(int v) {
        colors[v] = 1;
        for (int n : vertexes[v]) {
            if(colors[n] == 0) {
                haveCycle(n);
            }
            if(colors[n] == 1) {
                this.haveCycles = true;
                return;
            }
        }
        colors[v] = 2;
        return;
    }

    boolean isLinked() {
        for(int v : colors) {
            if(v == 0)
                return false;
        }
        return true;
    }





//5
    void floyd() {
        for (int i=0; i<n; ++i)
            for (int u=0; u<n; ++u)
                for (int v=0; v<n; ++v)
                    if (d[u][i] < Double.POSITIVE_INFINITY && d[i][v] < Double.POSITIVE_INFINITY)
                        d[u][v] = min (d[u][v], d[u][i] + d[i][v]);
    }





//6
package com.company;
import java.util.*;

class Graph {
    private final int countOfVertexes;
    private final HashSet<Integer>[] vertexes;

    Graph(int v) {
        countOfVertexes = v;
        vertexes = new HashSet[v];
        for (int i = 0; i < v; ++i)
            vertexes[i] = new HashSet();
    }

    //добавляем ребро в граф
    void addEdge(int root, int outGoing) {
        vertexes[root].add(outGoing);
    }

    Graph reverse() {
        Graph graphReverse = new Graph(countOfVertexes);

        for (int i = 0; i < countOfVertexes; ++i) {
            for (int root : this.vertexes[i]) {
                graphReverse.vertexes[root].add(i);
            }
        }
        return graphReverse;
    }

    void reverseVisit(LinkedList<Integer> list, int v, boolean[] visited) {
        visited[v] = true;

        for (int n : vertexes[v]) {
            if (!visited[n]) {
                reverseVisit(list, n, visited);
            }
        }
        list.addFirst(v);
    }

    void DFSReverse(LinkedList<Integer> list) {
        boolean[] visited = new boolean[countOfVertexes];

        for (int i = 0; i < countOfVertexes; ++i) {
            if (!visited[i]) {
                reverseVisit(list, i, visited);
            }
        }
    }

    void preVisitGraph(int v, int[] numSCC, int curSCC) {
        numSCC[v] = curSCC;
    }

    void visit(int v, int[] numSCC, int curSCC, boolean[] visited) {
        visited[v] = true;
        preVisitGraph(v, numSCC, curSCC);

        for (int n : vertexes[v]) {
            if (!visited[n]) {
                visit(n, numSCC, curSCC, visited);
            }
        }
    }

    void DFS(LinkedList<Integer> list, int[] numSCC) {
        int curSCC = 0;
        boolean[] visited = new boolean[countOfVertexes];
        for (int n : list) {
            if (!visited[n]) {
                visit(n, numSCC, curSCC++, visited);
            }
        }
    }

    Graph getMetaGraph(int[] numSCC, int countSCC) {
        Graph metaGraph = new Graph(countSCC);
        for (int i = 0; i < vertexes.length; ++i) {
            for (int vertex : vertexes[i]) {
                if (numSCC[i] != numSCC[vertex]) {
                    //добавляем и возвращаем true, если нет элемента, если элемент есть,
                    //возвращает false
                    metaGraph.vertexes[numSCC[i]].add(numSCC[vertex]);
                }
            }
        }
        return metaGraph;
    }

    static void printSCC(LinkedList<Integer>[] arrayOfListsNumSCC) {
        for (int i = 0; i < arrayOfListsNumSCC.length; ++i) {
            Iterator<Integer> j = arrayOfListsNumSCC[i].listIterator();
            System.out.print("SCC " + i + ": ");
            while (j.hasNext()) {
                int vertex = j.next();
                System.out.print(vertex + " ");
            }
            System.out.println();
        }
    }

    void print() {
        for (int i = 0; i < this.vertexes.length; ++i) {
            Iterator<Integer> j = this.vertexes[i].iterator();
            System.out.print(i + "   ");
            while (j.hasNext()) {
                int vertex = j.next();
                System.out.print(vertex + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        Graph graph = new Graph(n);

        for (int i = 0; i < n; ++i) {
            int root = scanner.nextInt();
            int outGoingVertex = scanner.nextInt();
            while (outGoingVertex != -1) {
                graph.addEdge(root, outGoingVertex);
                outGoingVertex = scanner.nextInt();
            }
        }
        Graph graphReverse = graph.reverse();

        //список всех вершин в порядке убывания их post-значений
        LinkedList<Integer> list = new LinkedList<>();

        graphReverse.DFSReverse(list);

        int[] numSCC = new int[n];

        graph.DFS(list, numSCC);

        int max = Integer.MIN_VALUE;
        for (int j : numSCC) {
            if (j > max) {
                max = j;
            }
        }
        //количество SCC
        int countSCC = max + 1;

        //массив SCC со списком входящих в каждую SCC вершин
        LinkedList<Integer>[] arrayOfListsNumSCC = new LinkedList[countSCC];

        for (int i = 0; i < arrayOfListsNumSCC.length; ++i) {
            arrayOfListsNumSCC[i] = new LinkedList();
        }
        for (int i = 0; i < numSCC.length; ++i) {
            arrayOfListsNumSCC[numSCC[i]].add(i);
        }

        printSCC(arrayOfListsNumSCC);

        Graph metaGraph = graph.getMetaGraph(numSCC, countSCC);

        System.out.println("Meta-graph:");

        metaGraph.print();
    }
}