Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.1 kB
13
Indexable
Never
class Solution {
public:
    
    vector<int> vec[100005];
    bool vis[100005];
    
    int subtree[100005];
    int ans;
    
    void dfs(int u){
        subtree[u] = 1;
        vis[u] = 1;
        int sz = -1;
        int eq = true;
        
        for(int i = 0 ; i < vec[u].size() ; i++){
            int v = vec[u][i];
            if(vis[v]) continue;
            dfs(v);
            subtree[u] += subtree[v];
            if(sz == -1){
                sz = subtree[v];
            }
            else{
                if(sz != subtree[v]){
                    eq = false;
                }
            }
        }
        if(eq){
            ans++;
        }
       // cout<<u<<"  "<<subtree[u]<<endl;
    }
    
    int countGoodNodes(vector<vector<int>>& edges) {
        
        ans = 0;
        
        for(int i = 0 ; i < edges.size() ; i++){
            int u = edges[i][0];
            int v = edges[i][1];
            
            vec[u].push_back(v);
            vec[v].push_back(u);
            vis[u] = 0;
            vis[v] = 0;
        }
        
        dfs(0);
        
        return ans;
    }
};
Leave a Comment