AD1-PA: 5.023s

package ad1.ss16.pa;

import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;

public class Network {

    private int N;
    private int M;

    private List<Integer> adjList[];

    private List<Integer> critical;
    private int[] low;
    private int[] parent;
    private int[] depth;

    private int[] cost;
    private boolean changed;
    private int comps;

    public class CriticalList implements List<Integer> {

        private int count;
        private boolean containArray[];

        public CriticalList(int N) {
            containArray = new boolean[N];
            count = 0;
        }

        @Override
        public int size() {
            return count;
        }

        @Override
        public boolean add(Integer integer) {
            if (!containArray[integer])
                count++;

            containArray[integer] = true;
            return true;
        }

        @Override
        public boolean contains(Object o) {
            return containArray[(Integer) o];
        }


        @Override
        public void clear() {
            Arrays.fill(containArray, false);
            count = 0;
        }

        @Override
        public boolean isEmpty() {
            return false;
        }

        @Override
        public Iterator<Integer> iterator() {
            return null;
        }

        @Override
        public Object[] toArray() {
            return new Object[0];
        }

        @Override
        public <T> T[] toArray(T[] a) {
            return null;
        }

        @Override
        public boolean remove(Object o) {
            return false;
        }

        @Override
        public boolean containsAll(Collection<?> c) {
            return false;
        }

        @Override
        public boolean addAll(Collection<? extends Integer> c) {
            return false;
        }

        @Override
        public boolean addAll(int index, Collection<? extends Integer> c) {
            return false;
        }

        @Override
        public boolean removeAll(Collection<?> c) {
            return false;
        }

        @Override
        public boolean retainAll(Collection<?> c) {
            return false;
        }

        @Override
        public Integer get(int index) {
            return null;
        }

        @Override
        public Integer set(int index, Integer element) {
            return null;
        }

        @Override
        public void add(int index, Integer element) {

        }

        @Override
        public Integer remove(int index) {
            return null;
        }

        @Override
        public int indexOf(Object o) {
            return 0;
        }

        @Override
        public int lastIndexOf(Object o) {
            return 0;
        }

        @Override
        public ListIterator<Integer> listIterator() {
            return null;
        }

        @Override
        public ListIterator<Integer> listIterator(int index) {
            return null;
        }

        @Override
        public List<Integer> subList(int fromIndex, int toIndex) {
            return null;
        }
    }

    @SuppressWarnings("unchecked")
    public Network(int n) {
        N = n;
        adjList = new List[N];
        critical = new CriticalList(N);
        cost = new int[N];
        changed = false;
        comps = -1;

        for (int i = 0; i < N; i++) {
            adjList[i] = new LinkedList<>();
        }

        Arrays.fill(cost, -1);

        low = new int[N];
        parent = new int[N];
        depth = new int[N];
    }

    public int numberOfNodes() {
        return N;
    }//O(1)

    public int numberOfConnections() {
        return M;
    }//O(1)

    public void addConnection(int v, int w) {//(O(n)
        if (v == w)
            return;
        if (!adjList[v].contains((Integer) w)) {
            adjList[w].add(v);
            M++;
            adjList[v].add(w);
            changed = true;
            comps = -1;
        }
    }

    public void addAllConnections(int v) {//(O(n)
        boolean[] visited = new boolean[N];
        visited[v] = true;
        for (int i : adjList[v])
            visited[i] = true;
        for (int i = 0; i < N; i++)
            if (!visited[i]) {
                adjList[i].add(v);
                M++;
                adjList[v].add(i);
                changed = true;
                comps = -1;
            }
    }

    public void deleteConnection(int v, int w) {//O(n)
        if (adjList[v].remove((Integer) w)) {
            adjList[w].remove((Integer) v);
            M--;
            changed = true;
            comps = -1;
        }
    }

    public void deleteAllConnections(int v) {//O(n^2)

        changed = !adjList[v].isEmpty();
        comps = changed ? -1 : comps;
        M -= adjList[v].size();

        for (int w : adjList[v]) {
            adjList[w].remove((Integer) v);
        }
        adjList[v].clear();
    }

    public int numberOfComponents() {

        if (comps != -1)
            return comps;

        criticalNodes();

        return comps;
    }//O(n+m)

    public boolean hasCycle() {
        return N - M != numberOfComponents();
    }//O(n+m)

    public int minimalNumberOfConnections(int start, int end) {

        if (cost[start] == 0 && !changed) {
            return cost[end];
        }
        changed = false;
        Arrays.fill(cost, -1);

        Queue<Integer> query = new ArrayBlockingQueue<Integer>(N);

        cost[start] = 0;
        query.add(start);

        while (!query.isEmpty()) {
            int ele = query.remove();

            for (int x : adjList[ele]) {
                if (cost[x] == -1) {
                    cost[x] = cost[ele] + 1;
                    query.add(x);
                }
            }
        }

        return cost[end];
    }//O(n+m)

    public List<Integer> criticalNodes() {//O(n+m) //DFS + Check

        if (comps != -1)
            return critical;

        comps = 0;
        critical.clear();
        Arrays.fill(depth, -1);

        for (int i = 0; i < N; i++) {
            if (depth[i] == -1) {
                parent[i] = -1;
                Foo(i);
                comps++;
            }
        }
        return critical;
    }

    private void Foo(int i) {
        if (parent[i] == -1)
            depth[i] = low[i] = 0;
        else
            depth[i] = low[i] = depth[parent[i]] + 1;
        int childs = 0;
        boolean is = false;

        for (int ni : adjList[i]) {
            if (depth[ni] == -1) {
                parent[ni] = i;
                Foo(ni);
                childs++;
                if (low[ni] >= depth[i])
                    is = true;
                if (low[ni] < low[i])
                    low[i] = low[ni];
            } else if (parent[i] != ni) {
                if (depth[ni] < low[i])
                    low[i] = depth[ni];
            }
        }

        if ((parent[i] != -1 && is) || (parent[i] == -1 && childs > 1))
            critical.add(i);
    }
}