Leetcode: Redundant Connection

This question is asked at Amazon and Google. 

In this problem we define a tree as an undirected graph that is connected and has no cycles. I am given a graph that started as a tree with n nodes labelled from 1 to n with one additional edge added. The added edge has 2 different vertices chosen from 1 to n, and the graph is represented as an array of edges of length n where edges[i] = [ai, bi] in the graph. 

Return an edge that can be removed so that the resulting graph is a tree of n nodes. 

You want to be able to make a tree, which indicates that you want to be able to make a cycle. 

The first diagram you can build a tree by removing anything. 

Let's go over both of the approaches now. 

Number 1 is DFS. It's a pretty simple approach. We look into each edge and see if we can connect u to v for each edge, and then see if there is a duplicate edge.

class Solution {

    Set<Integer> seen = new HashSet();

    int MAX_EDGE_VAL = 1000;

    public int[] findRedundantConnection(int[][] edges) {

        ArrayList<Integer> graph = new ArrayList[MAX_EDGE_VAL + 1]); 

        for(int i = 0; i <= MAX_EDGE_VAL; i++) {

            graph[i] = new ArrayList();

         }

        for(int[] edge: edges) {

            seen.clear();

            //return edge if we can go from one node to another, this is the edge to remove. 

            if(!graph[edge[0]].isEmpty() && !graph[edge[1]].isEmpty() && dfs(graph, edge[0], edge[1]) {

                return edge;

            }

            //add all the corresponding edges, this is how we build the graph. 

            graph[edge[0]].add(edge[1]);

            graph[edge[1]].add(edge[0]);

        }

        throw new AssertionError();

    }

    public boolean dfs(ArrayList<Integer>[] graph, int source, int target) {

        if(!seen.contains(source)) {

            seen.add(source);

            if(source == target) return true;

            //perform depth first search based on the nodes that are seen

            //for each node see if we can find the target. 

            for(int nei: graph[source]) {

                if (dfs(graph, nei, target)) return true;

            }

        }

        return false; 

    }

}

Another way we can go through this thing is to showcase disjoint sets. If we are given this data structure, we can use this in a straightforward manner to try to solve the problem. The 2 methods of the Disjoint set union are find and union. The find method outputs unique id so 2 nodes are in the same id if and only if they are the same component. We keep track of parent, remembering the id of.a smaller node, and we call a node the leader of a connected component if it is its own parent.

Union draws an edge (x, y) in the graph connecting find(x) and find(y) together. Here's the naive implementation:

function find(x):

#parent initialized as x -> x

    while parent[x] != x:

        x = parent[x]

    return x

function union(x, y): 

    #make y the parent of X as well. 

    parent[find[x]] = find(y)

There's also a few techniques that would be useful to know to better understand disjoint set union. 

1. Path compression - changing x = parent[x] to parent[x] = find(parent[x]), remembering the calculation when computing the correct parent for x. 

2. Union by rank - distributing the workflow of find across leaders evenly. We have 2 leaders xr, yr and we want to choose which one is the parent of which. The 2 choices are parent[x] = yr or parent[y] = xr. We choose the leader that has a new following. Rank means there is less than 2 ^ rank[x] followers of x. 

We simply find the first node that is not connected. 

Here's the solution:

class Solution {

    int MAX_EDGE_VAL = 1000;

    public int[] findRedundantConnection(int[][] edge) {

        DSU dsu = new DSU(MAX_EDGE_VAL + 1);

        //see if we find any interfering edge

//see if node is connected or not and have the same origin

        for(int[] edge: edges) {

            if(!dsu.union(edge[0], edge[1])) return edge;

        }

        throw new AssertionError();

    }

}

class DSU {

    int[] parent;

    int[] rank;

}

public DSU(int size) {

    //set each node parent to itself

    parent = new int[size];

    for(int i = 0; i < size; i++) parent[i] = i;

    rank = new int[size]; 

}

//find parent node

public int find(int x) {

    if(parent[x] != x) parent[x] = find(parent[x]);

    return parent[x];

}

//find the one with the highest rank, join them

//otherwise see if they have same origin 

public boolean union(int x, int y) {

    int xr = find(x), yr = find(y); 

    if(xr == yr) return false;

    else if (rank[xr] < rank[yr]) parent[xr] = yr;

    else if (rank[xr] > rank[yr]) parent[yr] = xr;

    else {

        parent[yr] = xr;

        rank[xr]++; 

    } 

}

}

This gives both the time and space complexity of O(N).