How can i avoid TLE for my solution for 1466 Reorder Routes to Make All Paths Lead to the City Zero
PaladinDanse
40
Graph TheoryQueue

Here is my complete solution. It passess 71 out of the 76 test cases but gets TLE after that

class Solution {
    public int minReorder(int n, int[][] connections) {
        int res=0;
        Queue<Integer> q = new LinkedList<>();
        int i=0;
        for(int [] c : connections)
        {
            if(c[0]==0)
            {
               res++;
               q.add(c[1]);
            }
            i++;
        }

        for(int [] c : connections){
            if(c[1]==0)
                q.add(c[0]);
        }
        Set<Integer> seen=new HashSet<>();
        seen.add(0);
        while(!q.isEmpty())
        {
            int x = q.poll();
            for(int [] c : connections){
                if(c[0]==x && !seen.contains(c[1]))
                {
                    q.add(c[1]);  
                    res++;
                }
                else
                {
                    if(c[1]==x && !seen.contains(c[0]))
                        q.add(c[0]);  
                }
            }
            seen.add(x);
        }
        
        return res;
    }
}

I think i can exit out of this loop early

            int x = q.poll();
            for(int [] c : connections){
                if(c[0]==x && !seen.contains(c[1]))
                {
                    q.add(c[1]);  
                    res++;
                }
                else
                {
                    if(c[1]==x && !seen.contains(c[0]))
                        q.add(c[0]);  
                }
            }
            seen.add(x);

but not sure how

Comments (0)