Untitled
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