GraphValidTree.java

package depth_first_search;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

/**
 * Created by gouthamvidyapradhan on 11/12/2017.
 * Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a
 * function to check whether these edges make up a valid tree.

 For example:

 Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

 Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

 Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the
 same as [1, 0] and thus will not appear together in edges.

 Solution O(E + V). A graph is a tree if there are no cycles and number of connected components is 1.
 */
public class GraphValidTree {

    private List[] graph;
    private BitSet done;
    /**
     * Main method
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception{
        int[][] graph =  {{1, 0}};
        System.out.println(new GraphValidTree().validTree(2, graph));
    }


    public boolean validTree(int n, int[][] edges) {
        graph = new List[n];
        done = new BitSet();
        for(int i = 0; i < n; i ++){
            graph[i] = new ArrayList<>();
        }
        for(int i = 0; i < edges.length; i ++){
            int u = edges[i][0];
            int v = edges[i][1];
            graph[u].add(v);
            graph[v].add(u);
        }

        int count = 0;
        for(int i = 0; i < n; i++){
            if(!done.get(i)){
                if(!dfs(graph, 0, -1)){
                    return false;
                }
                count ++; //count number of connected components
            }
        }
        return count <= 1;
    }

    private boolean dfs(List[] graph, int u, int p){
        done.set(u);
        List<Integer> children = graph[u];
        if(children != null){
            for(int c : children){
                if(p != c){ //should not be equal to parent
                    if(!done.get(c)){
                        if(!dfs(graph, c, u)){
                            return false;
                        }
                    } else{
                        return false;
                    }
                }
            }
        }
        return true;
    }


}