Why did my BFS/DFS solution TLE for ARRGRAPH?

general
,
1

As you may observe on the Submissions page, I made a ton of solutions to the ARRGRAPH problem, trying out several variations on BFS and DFS, in both Java and C++, but all of them gave TLE.

The editorial states that we should be able to check our graph is connected using DFS. Then why did my approach not work?

One of my submissions:

import java.util.*;

class Main {
    static int size = 1000;

    static int gcd(int a, int b){
        if(a % b == 0) return b;

        return gcd(b, a % b);
    }

    static boolean isConnected(int nos[]){
        // check if all numbers are same
        boolean allSame = true;
        int len = nos.length;
        
        for(int i = 1; i < len; i++){
            if(nos[i] != nos[i - 1]){
                allSame = false;
                break;
            }
        }

        if(allSame){
            return len == 1;
        }
        int adjList[][] = new int[size][size];
        int[] sizeList = new int[size];
        boolean[] visited = new boolean[size];
        boolean[] wasOriginallyPresent = new boolean[size];
        for(int i : nos) wasOriginallyPresent[i] = true;
        
        int a, b;
        for(int i = 0; i < len; i++){
            for(int j = i + 1; j < len; j++){
                a = nos[i]; b = nos[j];
                if(gcd(a, b) == 1){
                    adjList[a][sizeList[a]] = b;
                    adjList[b][sizeList[b]] = a;
                    sizeList[a]++;
                    sizeList[b]++;
                }
            }
        }
        
        // System.out.println("Adjaceny list");
        for(int i = 0; i > size; i++){
            int s = sizeList[i];
            if(s == 0) continue;
            System.out.print(i + ": ");
            for(int j = 0; j < s; j++){
                System.out.print(adjList[i][j] + " ");
            }
            System.out.println();
        }

        int i = 2;
        for(; i < size; i++){
            if(sizeList[i] > 0){
                break;
            }
        }

        if(i == size) {
            return false;
        }

        PriorityQueue<Integer> q = new PriorityQueue<Integer>();
        q.add(i);

        while(q.size() > 0){
            int num = q.remove(), x;
            visited[num] = true;

            for(int k = 0, len2 = sizeList[num]; k < len2; k++){
                x = adjList[num][k];
                if(!visited[x]){
                    visited[x] = true;
                    q.add(x);
                }
            }
        }

        for(int k = 0; k < len; k++){
            if(!visited[nos[k]] && wasOriginallyPresent[nos[k]]) return false;
        }

        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();
        
        while(T-- > 0){
            int n = sc.nextInt();
            int nos[] = new int[n];
            for(int i = 0; i < n; i++)
                nos[i] = sc.nextInt();

            boolean con = isConnected(nos);

            nos[0] = con ? nos[0] : 47;
            
            System.out.println(con ? 0 : 1);
            for(int i : nos)
                System.out.print(i + " ");
            
            System.out.println();
        }

        sc.close();
    }
}