C++ dfs solution.. easy


#1

vector v[100001];int cot=0;
bool vis[100001]={false};
void inl(int x)
{
cot=0;
for(int i=0;i<=x;i++)
vis[i]=false,v[i].clear();
}
void dfs(int x,int sum,vector &a,int c)
{
vis[x]=true;
sum+=a[x-1];bool b=true;
for(int i=0;i<v[x].size();i++)
{
if(!vis[v[x][i]])
{
b=false;
dfs(v[x][i],sum,a,c);
}
}
if(b && sum<=c) cot++;
sum-=a[x-1];
}
int Solution::solve(vector &A, vector<vector > &B, int C)
{
inl(A.size()+1);
for(int i=0;i<B.size();i++){
v[B[i][0]].push_back(B[i][1]);
v[B[i][1]].push_back(B[i][0]);
}
dfs(1,0,A,C);
return cot;
}