|
|
back to boardI am using priority queue. Priority is determined by the number of elements. The top element is one without parents. When it's removed from the queue, it's being deleted as a parent from all the other elements. I get WA#4. Any idea why? This is my code. Can someone tell me why do I get WA#4? import java.util.Collection; import java.util.Comparator; import java.util.HashSet; import java.util.Hashtable; import java.util.Iterator; import java.util.PriorityQueue; import java.util.Scanner; public class MartianCouncil { public static void main(String[] args) { Hashtable<Integer, TreeNode> global = new Hashtable<Integer, TreeNode>(); Scanner s = new Scanner(System.in); int n = s.nextInt(); if (n == 0) { s.close(); return; } s.nextLine(); for (int i = 1; i <= n; i++) { TreeNode node = global.get(i); if (node == null) { node = new TreeNode(i); global.put(i, node); } String line = s.nextLine(); String[] nums = line.split(" "); for (int j = 0; j < nums.length - 1; j++) { int num = Integer.parseInt(nums[j]); TreeNode nd = global.get(num); if (nd == null) { nd = new TreeNode(num); global.put(num, nd); } node.addChild(nd); } } s.close(); print(global); }
public static void print(Hashtable<Integer, TreeNode> global) { PriorityQueue<TreeNode> q = new PriorityQueue<TreeNode>(); q.addAll(global.values()); StringBuilder res = new StringBuilder(""); while (!q.isEmpty()) { TreeNode nd = q.poll(); res = res.append((res.length() == 0) ? "" : " "); res = res.append(nd.getNum()); } System.out.print(res); }
public static class TreeNode implements Comparable<MartianCouncil.TreeNode> {
private int num = 0; private Collection<MartianCouncil.TreeNode> children = new HashSet<MartianCouncil.TreeNode>(); private Collection<MartianCouncil.TreeNode> parents = new HashSet<MartianCouncil.TreeNode>();
public TreeNode(int num) { this.num = num; }
public int hashCode() { return num; }
public boolean equals(Object o) { if (o == null) { return false; } else if (!(o instanceof MartianCouncil.TreeNode)) { return false; } else { return (this.hashCode() == o.hashCode()); } }
public boolean addChild(MartianCouncil.TreeNode child) { child.parents.add(this); return children.add(child); }
public boolean removeChild(MartianCouncil.TreeNode child) { child.parents.remove(this); return children.remove(child); }
public boolean addParent(TreeNode parent) { parent.children.add(this); return parents.add(parent); }
public boolean removeParent(TreeNode parent) { parent.children.remove(this); return parents.remove(parent); }
public void removeAllChildren() { Iterator<TreeNode> it = children.iterator(); while (it.hasNext()) { TreeNode child = it.next(); child.parents.remove(this); } children.clear(); }
public int getNum() { return num; }
public Collection<TreeNode> getChildren() { return children; }
public int getParentsNum() { return parents.size(); } @Override public int compareTo(MartianCouncil.TreeNode nd) { return Math.round(Math.signum(this.getParentsNum() - nd.getParentsNum())); } }
public class TreeNodeComp implements Comparator<MartianCouncil.TreeNode> { @Override public int compare(MartianCouncil.TreeNode nd1, MartianCouncil.TreeNode nd2) { return Math.round(Math.signum(nd1.getParentsNum() - nd2.getParentsNum())); } }
} |
|
|