Advertisement
Guest User

Untitled

a guest
Apr 25th, 2017
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.53 KB | None | 0 0
  1. //package t68;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.FileReader;
  5. import java.io.PrintWriter;
  6. import java.util.ArrayList;
  7. import java.util.LinkedList;
  8. import static java.lang.Integer.parseUnsignedInt;
  9. import java.util.StringTokenizer;
  10.  
  11. public class T68 {
  12.  
  13. public static void main(String[] args) throws Exception {
  14. BufferedReader in = new BufferedReader(new FileReader("in.txt"));
  15. int n = parseUnsignedInt(in.readLine());
  16. ArrayList<LinkedList<Integer>> graf = new ArrayList<>(2 * n + 2);
  17. for (int i = 0; i < n; i++) {
  18. graf.add(new LinkedList<>());
  19. }
  20. String s;
  21. StringTokenizer st;
  22. for (int i = 0; i < n; i++) {
  23. s = in.readLine();
  24. st = new StringTokenizer(s, " ", false);
  25. st.nextToken();
  26. LinkedList<Integer> list = graf.get(i);
  27. while (st.hasMoreTokens()) {
  28. list.add(parseUnsignedInt(st.nextToken()) - 1);
  29. }
  30. }
  31. in.close();
  32.  
  33. LinkedList<Integer> bfs = new LinkedList<>();
  34. boolean[] visited = new boolean[n];
  35. int[] time = new int[n];
  36. boolean possible = false;
  37. int maxDropTime = -1, start = -1;
  38.  
  39. for (int i = 0; i < n; i++) {
  40. int localMaxTime = 0;
  41. for (int j = 0; j < n; j++) {
  42. visited[j] = false;
  43. }
  44. time[i] = 0;
  45. bfs.clear();
  46. visited[i] = true;
  47. bfs.add(i);
  48. int dropped = 1;
  49. while (!bfs.isEmpty()) {
  50. int v = bfs.remove();
  51. for (Integer sm : graf.get(v)) {
  52. if (!visited[sm]) {
  53. bfs.add(sm);
  54. dropped++;
  55. visited[sm] = true;
  56. time[sm] = time[v] + 1;
  57. if (time[sm] > localMaxTime) {
  58. localMaxTime = time[sm];
  59. }
  60. }
  61. }
  62. }
  63. if (dropped == n) {
  64. possible = true;
  65. if (localMaxTime >= maxDropTime) {
  66. maxDropTime = localMaxTime;
  67. start = i;
  68. }
  69. }
  70. }
  71.  
  72. PrintWriter out = new PrintWriter("out.txt");
  73. if (possible) {
  74. out.println(maxDropTime);
  75. out.print(start + 1);
  76. } else {
  77. out.print("impossible");
  78. }
  79. out.close();
  80. }
  81.  
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement