首页 > 滴滴9.13笔试第二题,有哪位大佬告诉我错哪了吗,提交爆0
头像
lofil
编辑于 2020-09-14 12:03
+ 关注

滴滴9.13笔试第二题,有哪位大佬告诉我错哪了吗,提交爆0

import java.util.*;

public class T2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        String[] res = new String[T];
        for(int i=0;i<T;i++){
            int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();
            Map<Integer,List<Integer>> adj = new HashMap<>();
            for(int j=0;j<m;j++){
                int a = sc.nextInt(), b = sc.nextInt(), v = sc.nextInt();
                if(v>k){continue;}
                if(!adj.containsKey(a)){
                    adj.put(a,new ArrayList<>());
                }
                if(!adj.containsKey(b)){
                    adj.put(b,new ArrayList<>());
                }
                adj.get(a).add(b);
                adj.get(b).add(a);
            }
            if(bfs(adj,n)){
//                res[i] = "YES";
                System.out.println("YES");
            }else{
//                res[i] = "NO";
                System.out.println("NO");
            }
        }
    }
    private static boolean bfs(Map<Integer,List<Integer>> adj, int n){
        if(adj.size()==0){return false;}
        int cnt = 0;
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        int root = adj.entrySet().iterator().next().getKey();
        queue.offer(root);
        visited.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0;i<size;i++){
                int cur = queue.poll();
                cnt++;
                for(int next: adj.get(cur)){
                    if(!visited.contains(next)){
                        queue.offer(next);
                        visited.add(next);
                    }
                }
            }
        }
        return cnt==n?true:false;
    }
}

全部评论

(2) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐