My C++ solution using DFS


  • -1
    J
    class Solution
    {
    public:
    	bool dfs(int n, unordered_map<int, vector<int>> &adjList, unordered_set<int> &visited)
    	{
    		if (adjList.find(n) == adjList.end())
    		{
    			visited.insert(n);
    			return true;
    		}
    		vector<int> v = adjList[n];
    		for (int i = 0; i < v.size(); i++)
    		{
    			if (visited.find(v[i]) != visited.end())
    			{
    				return false;
    			}
    			else
    			{
    				visited.insert(v[i]);
    				if (!dfs(v[i], adjList, visited))
    				{
    					return false;
    				}
    			}
    		}
    		return true;
    	}
    
    	bool validTree(int n, vector<pair<int, int>>& edges)
    	{
    		unordered_map<int, vector<int>> adjList;
    		for (int i = 0; i < edges.size(); i++)
    		{
    			if (adjList.find(edges[i].first) == adjList.end())
    			{
    				vector<int> v;
    				adjList[edges[i].first] = v;
    			}
    			adjList[edges[i].first].push_back(edges[i].second);
    		}
    
    		unordered_set<int> visited;
    		visited.insert(0);
    		if (!dfs(0, adjList, visited))
    		{
    			return false;
    		}
    		for (int i = 0; i < n; i++)
    		{
    			if (visited.find(i) == visited.end())
    			{
    				return false;
    			}
    
    		}
    		return true;
    	}
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.