Advertisement
Guest User

Untitled

a guest
Apr 25th, 2017
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.08 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.ArrayList;
  3. import java.util.StringTokenizer;
  4. import java.util.Vector;
  5.  
  6. final public class Main
  7. {
  8.  
  9.     public static ArrayList<ArrayList<Integer>> adjacencyList = new ArrayList<>();
  10.     public static int[] distances;
  11.     public static boolean[] isVisited;
  12.     public static int n;
  13.     public static int ex = 0;
  14.     public static int diam = 0;
  15.     public static int node = -1;
  16.     public static int numberOfVisited = 0;
  17.     public static Vector<Integer> queue = new Vector<>();
  18.  
  19.  
  20.     public static void bfs(int s)
  21.     {
  22.         queue.add(s);
  23.         distances[s] = 0;
  24.         isVisited[s] = true;
  25.         ex = 0;
  26.         numberOfVisited = 1;
  27.         while (!queue.isEmpty())
  28.         {
  29.             int v = queue.remove(0);
  30.             for (Integer i : adjacencyList.get(v))
  31.             {
  32.                 if (!isVisited[i])
  33.                 {
  34.                     queue.add(i);
  35.                     distances[i] = distances[v] + 1;
  36.                     isVisited[i] = true;
  37.                     numberOfVisited++;
  38.                     if (distances[i] > ex)
  39.                     {
  40.                         ex = distances[i];
  41.                     }
  42.                 }
  43.             }
  44.         }
  45.     }
  46.  
  47.     public static void check(int currNode)
  48.     {
  49.         if (numberOfVisited == n)
  50.         {
  51.             if (ex > diam)
  52.             {
  53.                 diam = ex;
  54.                 node = currNode;
  55.             }
  56.         }
  57.     }
  58.  
  59.     public static void update()
  60.     {
  61.         for (int i = 0;i < n; i++)
  62.         {
  63.             isVisited[i] = false;
  64.         }
  65.     }
  66.  
  67.     public static void solve()
  68.     {
  69.         for (int i = 0;i < n;i++)
  70.         {
  71.             bfs(i);
  72.             check(i);
  73.             update();
  74.         }
  75.     }
  76.  
  77.     public static void read(String inputPath) throws IOException
  78.     {
  79.         BufferedReader bf = new BufferedReader(new FileReader(inputPath));
  80.         n = Integer.parseInt(bf.readLine());
  81.         for (int i = 0;i < n;i++)
  82.         {
  83.             adjacencyList.add(new ArrayList<>());
  84.         }
  85.         distances = new int[n];
  86.         isVisited = new boolean[n];
  87.         String line;
  88.         int count = 0;
  89.         while((line = bf.readLine()) != null)
  90.         {
  91.             StringTokenizer st = new StringTokenizer(line," \t\r\n");
  92.             st.nextToken();
  93.             while(st.hasMoreTokens())
  94.             {
  95.                 adjacencyList.get(count).add(Integer.parseInt(st.nextToken())-1);
  96.             }
  97.             count++;
  98.         }
  99.     }
  100.  
  101.     public static void show()
  102.     {
  103.         for (int i = 0;i < n;i++)
  104.         {
  105.             System.out.println(i + " ->  " + adjacencyList.get(i));
  106.         }
  107.     }
  108.  
  109.     public static void main(String[] args) throws IOException
  110.     {
  111.         read("in.txt");
  112.         solve();
  113.         PrintWriter pr = new PrintWriter(new File("out.txt"));
  114.         if(node != -1)
  115.         {
  116.             pr.print(diam + "\n");
  117.             pr.print(node + 1);
  118.         }
  119.         else
  120.         {
  121.             pr.print("impossible");
  122.         }
  123.         pr.flush();
  124.  
  125.     }
  126. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement