Help in PERCAPTA

help
1

Here is my solution. Cannot figure out what’s wrong. I am using a simple BFS on the subgraph.

2

In your bfs, when you are poping out then you are marking it vis and pushing in vector. There may be cases that it was already in queue and it was again pushed because it was not marked visited.

queue <lld> q;
    q.push(u);
    vis[u]=1;
    temp.push_back(u);
    while(!q.empty())
    {
        int val=q.front();
        q.pop();
        for(int i=0;i<v[val].size();i++)
        {
            if(!vis[v[val][i]] && chose[v[val][i]])
            {
                q.push(v[val][i]);
                vis[v[val][i]]=1;
                temp.push_back(v[val][i]);
            }
        }
    }

https://www.codechef.com/viewsolution/34635997

2 Likes
3

Oh makes sense. I didn’t think much about it. I believe I have done it as it is done implemented for Djikstra’s algorithm. Can you give an example of where the same city will be pushed multiple times in the vector? I can’t think of any

4

Got it. I was assuming that the graph is a tree. Found a counterexample easily.

5

Oh good

6

will u guys plz help me with my solution> @udayan14 @sebastian
its giving RE but working fine with sample inputs and random inputs i tried for testing
thanks in advance:::::]
import collections

    def dfs(p):
      
        visited.add(p)
        temp.add(p+1)
        for node in road[p]:
            if(node not in visited and selected[node]):
                
                dfs(node)
        
    t=int(input())
    for _ in range(t):
        n,m=map(int,input().split())
        income=list(map(int,input().split()))
        pop=list(map(int,input().split()))
        road=collections.defaultdict(list)
        for __ in range(m):
            a,b=map(int,input().split())
            road[a-1].append(b-1)
            road[b-1].append(a-1)
        i=income[0]
        p=pop[0]
        # to find max per capita
        for x in range(1,n):
            if(i*pop[x]<p*income[x]):
                i=income[x]
                p=pop[x]
        
        
        selected=[False]*n
        # to select node with max per capita
        for x in range(n):
            if(pop[x]*i== income[x]*p):
                selected[x]=True
        
        visited=set()
        ans=set()
        
        for each in range(n):
            
            if(each not in visited and selected[each]):
                temp=set()
                dfs(each)
                if(len(temp)>len(ans)):
                    ans=temp
        print(len(ans))
        print(*ans)
7

You are doing the same mistake as me. Add a node p to the visited before calling dfs§

8

is this is for my code @udayan14

9

yes

10

but brother ,the first thing i am doing in dfs is marking the node on which it is being called visited .hence i don’t think that same as ur mistake .
i might be wrong don’t mind plz,
can u help me with some corner cases so that i can debug.

11
12

But this should give WA. He is getting RE

13

i Understand ,what u said but could not co-relate with my problem .
i tried running my dfs() as u said but its working fine ,even if there will be repeating number in stack of recursion(since i used recursive) it wont tamper my ans since i am storing nodes of connected component into set named temp.
the thing which is bothering me the most is the o/p,which is giving RE instead of WA (if my logic is wrong)
Neither TLE .
sorry for not understanding…
but i am trying my best …

14

I see that you have used set(), so the order of marking nodes visited doesn’t matter in your case. I am not that proficient in python to figure out why the RE is occuring.

15

thanks for your efforts brother .
if can just tag someone who know well python and can help me.
btw u r right in what u said about set().