头像

养乐多是乳酸菌




离线:1天前



题目链接 PAT甲级1013 https://pintia.cn/problem-sets/994805342720868352/problems/994805500414115840

我遇到了java最后一个测试点的超时问题。

错误的代码:

import java.util.*;
import java.io.*;
class Main{
    public static ArrayList<Integer>[] ar;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] first = br.readLine().split(" ");
        int N = Integer.parseInt(first[0]);
        int M = Integer.parseInt(first[1]);
        int K = Integer.parseInt(first[2]);
        ar = new ArrayList[N + 1];
        for(int x = 0; x < N + 1; x++){
            ArrayList<Integer> list = new ArrayList<>();
            ar[x] = list;
        }
        for(int i = 0; i < M; i++){
            String[] tmp = br.readLine().split(" ");
            int one = Integer.parseInt(tmp[0]);
            int two = Integer.parseInt(tmp[1]);
            ar[one].add(two);
            ar[two].add(one);
        }
        String[] third = br.readLine().split(" ");
        for(int j = 0; j < K; j++){
            int checkedNum = Integer.parseInt(third[j]); 
            System.out.println(prictice(checkedNum));
        }
    }
    public static int prictice(int checkedNum){
        int count = 0;
        int[] visited = new int[ar.length];
        for(int k = 1; k < ar.length; k++){
            if(k == checkedNum || visited[k] == 1){
                continue;
            }
            count++;
            dfs(k, visited, checkedNum);
        }
        return count - 1;
    }
    public static void dfs(int num, int[] visited, int checkedNum){
        if(visited[num] == 1 || num == checkedNum){
            return;
        }
        visited[num] = 1;
        for(int number : ar[num]){
            dfs(number, visited, checkedNum);
        }
    }
}

请问有没有Java这道题的题解,或者指出如何改进?