C++ BFS solution with explaination


  • 0
    J
    class Solution {
    public:
    	bool validTree(int n, vector<pair<int, int>>& edges) {
            //queue for node(0~n-1)
    		queue<int> Q;
    		int len = edges.size();
            //visited edges
    		vector<int> visited(len, false);
    		//visited nodes
            vector<int> nodeVisited(n, false);
            //no cyclic and every node is connectted len == n-1
    		if (len != n - 1)
    			return false;
    		if (len == 0)
    			return true;
    		
    		Q.push(edges[0].first);
    		nodeVisited[edges[0].first] = true;
    		while (!Q.empty())
    		{
    			int sz = Q.size();
    			for (int i = 0; i<sz; i++)
    			{
    				int x = Q.front();
    				Q.pop();
    				for (int j = 0; j<len; j++)
    				{
    					if (visited[j] == true)
    						continue;
    					if (edges[j].first == x || edges[j].second==x)
    					{
    						int y = edges[j].first == x? edges[j].second:edges[j].first;
                            //cyclic detected
    						if (nodeVisited[y])
    							return false;
    						nodeVisited[y] = true;
    						Q.push(y);
    						visited[j] = true;
    					}
    				}
    			}
    		}		
    		return true;
    
    	}
    };
    

Log in to reply
 

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