fork(2) download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.BufferedWriter;
  3. import java.io.IOException;
  4. import java.io.InputStreamReader;
  5. import java.io.OutputStreamWriter;
  6. import java.io.PrintWriter;
  7. import java.util.ArrayList;
  8. import java.util.HashMap;
  9. import java.util.LinkedList;
  10. import java.util.List;
  11. import java.util.Queue;
  12.  
  13. /**
  14.  * @author smundhra
  15.  * 
  16.  */
  17.  
  18. /*
  19.  
  20.  */
  21. public class Main {
  22.  
  23. 	/**
  24. 	 * @param args
  25. 	 * @throws IOException
  26. 	 * @throws NumberFormatException
  27. 	 */
  28. 	public static void main(String[] args) throws NumberFormatException,
  29. 			IOException {
  30.  
  31. 		// BufferedInputStream in = new BufferedInputStream(new FileInputStream(
  32. 		// "C:\\CodeChef\\smundhra\\src\\lifeUniverseAndEverything\\Input"));
  33. 		// System.setIn(in);
  34.  
  35. 		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
  36. 		PrintWriter pw = new PrintWriter(new BufferedWriter(
  37. 				new OutputStreamWriter(System.out)));
  38.  
  39. 		int t = Integer.parseInt(bf.readLine());
  40. 		// long t1 = System.currentTimeMillis();
  41. 		while (t > 0) {
  42. 			Graph g = new Graph(bf);
  43. 			for (Node n : g.hm.keySet())
  44. 				g.getAvgDistance(n);
  45. 			pw.printf(g.mostPopfriend.getN() + " " + "%f" + "\n", g
  46. 					.getMinDist());
  47.  
  48. 			t--;
  49.  
  50. 		}
  51. 		pw.flush();
  52. 		bf.close();
  53. 		// long diff = System.currentTimeMillis() - t1;
  54. 		// pw.print(diff);
  55. 		pw.close();
  56.  
  57. 	}
  58.  
  59. }
  60.  
  61. class Node {
  62.  
  63. 	int n;
  64. 	int distance;
  65.  
  66. 	@Override
  67. 	public int hashCode() {
  68. 		final int prime = 31;
  69. 		int result = 1;
  70. 		result = prime * result + n;
  71. 		return result;
  72. 	}
  73.  
  74. 	@Override
  75. 	public boolean equals(Object obj) {
  76. 		if (this == obj)
  77. 			return true;
  78. 		if (obj == null)
  79. 			return false;
  80. 		if (getClass() != obj.getClass())
  81. 			return false;
  82. 		Node other = (Node) obj;
  83. 		if (n != other.n)
  84. 			return false;
  85. 		return true;
  86. 	}
  87.  
  88. 	public int getDistance() {
  89. 		return distance;
  90. 	}
  91.  
  92. 	public void setDistance(int distance) {
  93. 		this.distance = distance;
  94. 	}
  95.  
  96. 	public int getN() {
  97. 		return n;
  98. 	}
  99.  
  100. 	public void setN(int n) {
  101. 		this.n = n;
  102. 	}
  103.  
  104. 	public Node(int n) {
  105. 		this.n = n;
  106. 	}
  107.  
  108. 	private boolean isVisited;
  109.  
  110. 	public boolean isVisited() {
  111. 		return isVisited;
  112. 	}
  113.  
  114. 	public void setVisited(boolean isVisited) {
  115. 		this.isVisited = isVisited;
  116. 	}
  117.  
  118. }
  119.  
  120. class Graph {
  121. 	int nodeCount;
  122. 	public HashMap<Node, ArrayList<Node>> hm;
  123. 	Integer[] s;
  124. 	Node mostPopfriend;
  125. 	double minDist = Double.MAX_VALUE;
  126. 	List<Node> nodeList = new ArrayList<Node>();
  127.  
  128. 	public Graph(BufferedReader bf) throws NumberFormatException, IOException {
  129. 		this.nodeCount = Integer.parseInt(bf.readLine());
  130.  
  131. 		hm = new HashMap<Node, ArrayList<Node>>();
  132. 		int i;
  133.  
  134. 		for (i = 1; i <= nodeCount; i++) {
  135. 			Node node = new Node(i);
  136. 			nodeList.add(node);
  137. 			hm.put(node, new ArrayList<Node>());
  138. 		}
  139. 		for (i = 1; i <= nodeCount; i++) {
  140. 			String a[] = bf.readLine().split(" ");
  141. 			List<Node> l = hm.get(new Node(i));
  142.  
  143. 			for (String s : a) {
  144. 				l.add(nodeList.get(Integer.parseInt(s) - 1));
  145. 			}
  146. 		}
  147. 	}
  148.  
  149. 	public void getAvgDistance(Node head) {
  150. 		for (Node node : hm.keySet()) {
  151. 			node.setVisited(false);
  152. 			node.setDistance(0);
  153. 		}
  154.  
  155. 		double totalDist = 0D;
  156.  
  157. 		Queue<Node> q = new LinkedList<Node>();
  158. 		q.add(head);
  159. 		head.setVisited(true);
  160. 		while (!q.isEmpty()) {
  161. 			Node node = q.poll();
  162.  
  163. 			for (Node n1 : hm.get(node)) {
  164. 				if (n1 == null)
  165. 					break;
  166. 				if (!n1.isVisited()) {
  167. 					n1.setDistance(node.getDistance() + 1);
  168. 					n1.setVisited(true);
  169. 					q.add(n1);
  170. 					totalDist += n1.getDistance();
  171. 				}
  172. 			}
  173. 		}
  174. 		double avgDistance = totalDist / (double) nodeCount;
  175. 		if (avgDistance <= this.minDist) {
  176. 			this.minDist = avgDistance;
  177. 			this.mostPopfriend = head;
  178. 		} else if (avgDistance == this.minDist) {
  179. 			if (this.mostPopfriend == null)
  180. 				this.mostPopfriend = head;
  181. 			if (this.mostPopfriend.getN() > head.getN())
  182. 				this.mostPopfriend = head;
  183. 		}
  184.  
  185. 	}
  186.  
  187. 	public double getMinDist() {
  188. 		return minDist;
  189. 	}
  190. }
Success #stdin #stdout 0.06s 213312KB
comments (?)
stdin
copy 
1
2
2
1
stdout
copy 
2 0.500000
https://ideone.com/XZRc1
language:
Java (HotSpot 12)
created:
14 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!