Treating input as graph, making sure no cycles and one connected component.


  • 1
    C

    There is probably an easier way to do this.... This is the first thing that came to my mind:

    I treat the input as an undirected graph, and

    1. Make sure there are no cycles.
    2. Check if it is just one connected component.
    class Solution {
    
        typedef unordered_set<int> Bucket;
        typedef vector<Bucket> AdjList;
    
        AdjList adjList;
        vector<bool> visited;
        vector<int> ccParent;
        
        void initialize(int n, vector<pair<int, int>>& edges) {
            visited  = vector<bool>(n, false);
            ccParent = vector<int>(n, -1);
            for (int i=0; i<n; i++) { adjList.push_back(Bucket()); }
            for (const pair<int, int>& pft : edges) {
                adjList[pft.first].insert(pft.second);
                adjList[pft.second].insert(pft.first);
            }
        }
        
        bool dfs(int parent, int node, int ccpar) {
            visited[node]  = true;
            ccParent[node] = ccpar;
            for (const int& neigh : adjList[node]) {
                if (neigh == parent) continue; //skip parent
                if (visited[neigh]) return false;
                if (dfs(node, neigh, ccpar) == false) return false;
            }
            return true;
        }
        
    public:
    
        bool validTree(int n, vector<pair<int, int>>& edges) {
            initialize(n, edges);
            
            for (int n=0; n<adjList.size(); n++) {
                if (visited[n]) continue;
                if (dfs(-1, n, n) == false) return false; //detected cycle
            }
            int ccpar = ccParent[0];
            for (int i=1; i<adjList.size(); i++) {
                if (ccParent[i] != ccpar) return false; //not one connected component
            }
            return true;
        }
    };

  • 0
    C

    I just realized that this probably doesn't handle self-loops or parallel edges. I'll need to create a test case or two, and handle it during the initialization part.


Log in to reply
 

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