能帮我看看我写的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,和骗分差不多了
