能帮我看看我写的8.30携程笔试第三题哪里有问题吗?

import java.util.*;
class TreeNode1 {
    int key;
    char color;
    List<TreeNode1> neibors = new ArrayList<>();
}
public class Main6 {
    public boolean DFS(TreeNode1 head,boolean[] flag,boolean[] isVisited) {
        if(head.color == 'r') flag[0] = true;
        else if(head.color == 'g') flag[1] = true;
        else flag[2] = true;
        if(flag[0]&&flag[1]&&flag[2]) return true;
        for(int i = 0;i<head.neibors.size();i++){
            TreeNode1 neibor = head.neibors.get(i);
            if(!isVisited[neibor.key]){
                isVisited[neibor.key] = true;
                if(DFS(neibor,flag,isVisited)){
                    return true;
                }
            }
        }
        return flag[0]&&flag[1]&&flag[2];
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        String color = in.nextLine();
        char[] charArray = color.toCharArray();
        TreeNode1[] tree = new TreeNode1[n];
        int result = 0;
        Main6 main = new Main6();
        while(n>1){
            int i = in.nextInt();
            int j = in.nextInt();
            i-=1;
            j-=1;
            if(tree[i] == null) {
                tree[i] = new TreeNode1();
                tree[i].key = i;
                tree[i].color = charArray[i];
            }
            if(tree[j]==null){
                tree[j] = new TreeNode1();
                tree[j].key = j;
                tree[j].color = charArray[j];
            }
            tree[i].neibors.add(tree[j]);
            tree[j].neibors.add(tree[i]);
            n--;
        }
        Set<String> cutSet = new HashSet<>();
        for(int i = 0;i<tree.length;i++){
            for(int j = 0;j<tree[i].neibors.size();j++){
                TreeNode1 delet = tree[i].neibors.get(j);
                StringBuilder cut = new StringBuilder(i+","+tree[i].neibors.get(j).key);
                if(!cutSet.contains(cut.toString())){
                    cutSet.add(cut.toString());
                    cut.reverse();
                    cutSet.add(cut.toString());
                    boolean[] isVisited = new boolean[tree.length];
                    isVisited[i] = true;
                    isVisited[delet.key] = true;
                    if(main.DFS(tree[i],new boolean[3],isVisited)&&main.DFS(delet,new boolean[3],isVisited)){
                        result ++;
                    }
                }
            }
        }
        System.out.println(result);
    }
}
暴力删除边+DFS检测删除后生成的俩颗树是否符合条件
只过了百分之6.21,和骗分差不多了

#携程##携程笔试#
全部评论

相关推荐

我即大橘:耐泡王
点赞 评论 收藏
分享
尊嘟假嘟点击就送:加v细说,问题很大
点赞 评论 收藏
分享
2 收藏 评论
分享
牛客网
牛客企业服务