1 / 2
Aug 2019

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;
}

}

  • created

    Aug '19
  • last reply

    Aug '19
  • 1

    reply

  • 573

    views

  • 2

    users

  • 2

    links

Suggested Topics

Want to read more? Browse other topics in Online Judge System or view latest topics.