Here is my code, i am getting tle using dfs. Can anyone suggest me a better approach than this? Thanks in advance.
#include
#include<bits/stdc++.h>
using namespace std;
void dfs(vector<vector> a,int *visited,int index,int *weight,int *persons,int *weights)
{
if(visited[index]) return ;
visited[index]=1;
*persons+=1;
*weight+=weights[index];
for(int i=0;i<a[index].size();i++)
{
dfs(a,visited,a[index][i],weight,persons,weights);
}
}
int main()
{
while(1){
int n,weight,result=0;
cin>>n>>weight;
if(n==0 && weight==0) break;
int weights[n+1];
vector<vector> a(n+1);
int visited[n+1];
for(int i=0;i<n;i++) {cin>>weights[i]; visited[i]=0; }
for(int i=0;i<n;i++)
{
int size;
cin>>size;
a[i].resize(size);
for(int j=0;j<size;j++) { int temp; cin>>temp; a[i][j]=temp-1; }
}
for(int i=0;i<n;i++)
{
int alweight=0,persons=0;
if(!visited[i]) {
dfs(a,visited,i,&alweight,&persons,weights);
if(alweight<=weight) result=max(result,persons);
}
}
cout<<result<<endl;
}
}
