C++ DFS Standard


#1
int result;
int num;
void dfs(int v, int count, vector<int> &A, vector<bool> vis, vector<vector<int>> &arr){
    vis[v]=1;
    
    for(int child: arr[v]){
        if(vis[child]==0){
            if(A[child-1]) dfs(child, count+1, A, vis, arr);
            else dfs(child, count, A, vis, arr);
        }
    }
    if(arr[v].size()==1 && count<=num) result++;
}

int Solution::solve(vector<int> &A, vector<vector<int> > &B, int C) {
    int n=A.size();
    result=0;
    num=C;
    vector<bool> vis(n+1, false);
    vector<vector<int>> arr(n+1);
    
    for(int i=0; i<n-1; i++){
        arr[B[i][0]].push_back(B[i][1]);
        arr[B[i][1]].push_back(B[i][0]);
    }

    if(A[0]==1) dfs(1, 1, A, vis, arr);
    else dfs(1, 0, A, vis, arr);
    return result;
}

#2
 if(arr[v].size()==1 && count<=num) result++;
Why arr[v].size() as one?

#3

Here graph is represented as adjacency list, so if any node has list of size of 1, it represents that node is a leaf node.


#4

I have done the same thing but it is giving me time limit exceeded . why? can you help

int result;
void dfs(int i,int visited[],vector adj[],int n,vector a,int c,int prev)
{
visited[i]=1;
if(a[i-1]==1)
c=c-1;
if(adj[i].size()==1)
{
if(c>=0)
{
result=result+1;
return ;
}
else
return ;
}
else
{
for(auto x: adj[i])
{
if(visited[x]!=1)
dfs(x,visited,adj,n,a,c,i);
}
return ;
}

}
int Solution::solve(vector &a, vector<vector > &v, int c) {
int n=a.size();
result=0;
vector adj[n+1];
for(int i=0;i<n-1;i++)
{
adj[v[i][0]].push_back(v[i][1]);
adj[v[i][1]].push_back(v[i][0]);
}
int visited[n+1]={0};
dfs(1,visited,adj,n,a,c,0);
return result;
}