Problem:

You are given an undirected connected graph. An articulation point (or cut vertex) is defined as a vertex which, when removed along with associated edges, makes the graph disconnected (or more precisely, increases the number of connected components in the graph). The task is to find all articulation points in the given graph.

Input:
The input to the function/method consists of three arguments:

• numNodes, an integer representing the number of nodes in the graph.
• numEdges, an integer representing the number of edges in the graph.
• edges, the list of pair of integers – A, B representing an edge between the nodes A and B.

Output:
Return a list of integers representing the critical nodes.

Example:

Input: numNodes = 7, numEdges = 7, edges = [[0, 1], [0, 2], [1, 3], [2, 3], [2, 5], [5, 6], [3, 4]]

Solution:

Logic:

• First find all the numbers in the connected graph into a unique set
• Order the list of pairs such in ascendence of the first pair element.
• For every element in the unique set,
  • find all the connected edges (pairs) which does not contain this element
  • Pick the first pair from these and build a list of all the elements that can be reached for this pair.
  • Then check if this list size is one less than the size of the unique elements, if so that means the graph is connected, if not then this element is critical. Add this element to the connections set
• Return the list of these connections.

You with me? critical yeah!

import java.util.*;

public class CriticalRouters {

    public static void main(String[] args) {
        List<PairInteger> pairs = new ArrayList<>();
        pairs.add(new PairInteger(0, 1));
        pairs.add(new PairInteger(0, 2));
        pairs.add(new PairInteger(1, 3));
        pairs.add(new PairInteger(2, 3));
        pairs.add(new PairInteger(2, 5));
        pairs.add(new PairInteger(5, 6));
        pairs.add(new PairInteger(3, 4));

        Set<Integer> vertexes = criticalRoutersList(7, 7, pairs);
        for (Integer v : vertexes) {
            System.out.print(" " + v + ", ");
        }

    }

    public static Set<Integer> criticalRoutersList(int nodesNum, int edgesNum, List<PairInteger> pairs) {
        Set<Integer> uniqueSet = new HashSet<>();
        Set<Integer> connections = new HashSet<>();
        Collections.sort(pairs, (a, b) -> Integer.compare(a.first, b.first));
        pairs.stream().forEach(list -> {
            uniqueSet.add(list.first);
            uniqueSet.add(list.second);
        });

        for (Integer value : uniqueSet) {
            List<PairInteger> newPairs = new ArrayList<>();
            for (PairInteger paire : pairs) {
                if (paire.first != value && paire.second != value) {
                    newPairs.add(paire);
                }
            }
            Set<Integer> buildList = new TreeSet<>(Arrays.asList(newPairs.get(0).first, newPairs.get(0).second));
            for (int inner = 1; inner < newPairs.size(); inner++) {
                mergeTag(buildList, newPairs.get(inner));
            }
            if (buildList.size() < uniqueSet.size() - 1) {
                connections.add(value);
            }
        }

        return connections;

    }


    private static void mergeTag(Set<Integer> buildList, PairInteger pairString) {
        if (buildList.contains(pairString.first) && buildList.contains(pairString.second))
            return;
        if (buildList.contains(pairString.first)) {
            buildList.add(pairString.second);
        } else if (buildList.contains(pairString.second)) {
            buildList.add(pairString.first);
        }
    }
}

public class PairInteger {
    int first;
    int second;

    public PairInteger(int first, int second) {
        this.first = first;
        this.second = second;
    }
}