package leetcode;
/*
 * 
 * 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.

Hint:

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? 
Is this case a valid tree?
Show More Hint 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.
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class GraphValidTree {
	HashSet<Integer> set = new HashSet<Integer>();
	HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
	public boolean validTree(int n, int[][] edges){
		HashSet<Integer> visited = new HashSet<Integer>();
		for(int[] edge:edges){
			if(!map.containsKey(edge[0]))
				map.put(edge[0], new ArrayList<Integer>());
			map.get(edge[0]).add(edge[1]);
			if(!map.containsKey(edge[1]))
				map.put(edge[1], new ArrayList<Integer>());
			map.get(edge[1]).add(edge[0]);			
		}
		if(edges.length == 0) return n==1;
		if(dfs(edges[0][0],null,visited))
			return set.size() == n;
		else {
			return false;
		}
	}
	private boolean dfs(Integer key,Integer parent,HashSet<Integer> visited){
	    if(set.contains(key)) return true;
		if(visited.contains(key))
			return false;
		visited.add(key);
		for(Integer child:map.get(key)){
		    if(child.equals(parent)) continue;
			if(!this.dfs(child, key, visited))
			    return false;
		}
		visited.remove(key);
		set.add(key);
		return true;
	}
}