关注
就A了第二题 package Qunar; import java.util.ArrayList; import java.util.HashSet; import java.util.Scanner; public class Main2 { //并查集 public static void main(String[] args) { Scanner scan = new Scanner(System.in); while(scan.hasNext()) { int p = scan.nextInt(); //p人 int n = scan.nextInt(); //n个关系 scan.nextLine(); String input = scan.nextLine(); // String s = ""; HashSet<String> names = new HashSet<>(); String[] relations = input.split(" "); for (int i = 0; i < relations.length; i++) { names.add(relations[i]); } ArrayList<Node> nodes = new ArrayList<Node>(); Node node; //建好所有节点 for (String s2: names) { node = new Node(s2); nodes.add(node); } //遍历所有关系 for (int i = 0; i < relations.length; i+=2) { Node n1 = new Node(relations[i]); Node n2 = new Node(relations[i+1]); int i1 = nodes.indexOf(n1); int i2 = nodes.indexOf(n2); if(i1!=-1&&i2!=-1) { nodes.remove(n1); nodes.remove(n2); if(n1.parents.size()==0) n1.union(n2); else n2.union(n1); nodes.add(n1); } else if(i1!=-1) { //找i2的位置 for (Node no: nodes) { Node pa = no.getParent(n2); if(pa !=null) { nodes.remove(n1); pa.union(n1); break; } } } else if(i2!=-1) { for (Node no: nodes) { Node pa = no.getParent(n1); if(pa != null) { nodes.remove(n2); pa.union(n2); break; } } } } if(nodes.size() >1) { System.out.println("DISCONNECTED"); } else { System.out.println(nodes.get(0).height()); } } scan.close(); } } class Node { ArrayList<Node> parents = new ArrayList<>(); public String name; Node(String s) { name = s; } void union(Node parent) { for(Node n: parents) { if(n.name.equals(parent.name)) return; } parents.add(parent); } Node getParent(Node node) { if(parents.size() == 0) { if(this.name.equals(node.name)) return this; else return null; } else { for (Node n: parents) { return n.getParent(node); } } return null; } int height() { if(this.parents.size() ==0) { return 0; } int max = 0; for (Node no: parents) { max = Math.max(no.height()+1, max); } return max; } @Override public boolean equals(Object obj) { // TODO Auto-generated method stub return ((Node)obj).name.equals(this.name); } } /** ** 4 2 A B C D */
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
转发
投递阿里巴巴控股集团等公司10个岗位 >
点赞 评论 收藏
转发
04-03 23:15
中国石油大学(华东) 计算机类 点赞 评论 收藏
转发
点赞 评论 收藏
转发
投递中国邮政储蓄银行等公司7个岗位 > 机械制造2024笔面经
点赞 评论 收藏
转发
牛客热帖
正在热议
# 牛客帮帮团来啦!有问必答 #
375360次浏览 7534人参与
# 在国企工作的人,躺平了吗? #
71075次浏览 859人参与
# 简历中的项目经历要怎么写 #
377088次浏览 6349人参与
# 应届生初入职场,求建议 #
21636次浏览 535人参与
# 晒一晒我的offer #
2789397次浏览 49651人参与
# 非技术岗薪资爆料 #
6458次浏览 131人参与
# 你更愿意参加线上面试还是线下面试? #
6207次浏览 90人参与
# 华为求职进展汇总 #
437346次浏览 4400人参与
# 租房前辈的忠告 #
20500次浏览 1619人参与
# 第一次面试 #
15230次浏览 236人参与
# 应届生应该先就业还是先择业 #
11845次浏览 113人参与
# 安利/避雷我的岗位 #
121868次浏览 2747人参与
# 机械人怎么评价今年的华为 #
53412次浏览 438人参与
# 谈薪时HR压价该怎么应对 #
32796次浏览 202人参与
# 通信硬件薪资爆料 #
143726次浏览 1059人参与
# 毕业租房也有小确幸 #
19666次浏览 1241人参与
# 除了offer,现在你还缺点啥? #
2479次浏览 50人参与
# 找工作,你会甘心进小厂还是猛冲大厂 #
22576次浏览 216人参与
# 来聊聊机械薪资天花板是哪家 #
20130次浏览 162人参与
# 如何确定求职岗位 #
101921次浏览 2416人参与