Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.ArrayList;
- import java.util.StringTokenizer;
- import java.util.Vector;
- final public class Main
- {
- public static ArrayList<ArrayList<Integer>> adjacencyList = new ArrayList<>();
- public static int[] distances;
- public static boolean[] isVisited;
- public static int n;
- public static int ex = 0;
- public static int diam = 0;
- public static int node = -1;
- public static int numberOfVisited = 0;
- public static Vector<Integer> queue = new Vector<>();
- public static void bfs(int s)
- {
- queue.add(s);
- distances[s] = 0;
- isVisited[s] = true;
- ex = 0;
- numberOfVisited = 1;
- while (!queue.isEmpty())
- {
- int v = queue.remove(0);
- for (Integer i : adjacencyList.get(v))
- {
- if (!isVisited[i])
- {
- queue.add(i);
- distances[i] = distances[v] + 1;
- isVisited[i] = true;
- numberOfVisited++;
- if (distances[i] > ex)
- {
- ex = distances[i];
- }
- }
- }
- }
- }
- public static void check(int currNode)
- {
- if (numberOfVisited == n)
- {
- if (ex > diam)
- {
- diam = ex;
- node = currNode;
- }
- }
- }
- public static void update()
- {
- for (int i = 0;i < n; i++)
- {
- isVisited[i] = false;
- }
- }
- public static void solve()
- {
- for (int i = 0;i < n;i++)
- {
- bfs(i);
- check(i);
- update();
- }
- }
- public static void read(String inputPath) throws IOException
- {
- BufferedReader bf = new BufferedReader(new FileReader(inputPath));
- n = Integer.parseInt(bf.readLine());
- for (int i = 0;i < n;i++)
- {
- adjacencyList.add(new ArrayList<>());
- }
- distances = new int[n];
- isVisited = new boolean[n];
- String line;
- int count = 0;
- while((line = bf.readLine()) != null)
- {
- StringTokenizer st = new StringTokenizer(line," \t\r\n");
- st.nextToken();
- while(st.hasMoreTokens())
- {
- adjacencyList.get(count).add(Integer.parseInt(st.nextToken())-1);
- }
- count++;
- }
- }
- public static void show()
- {
- for (int i = 0;i < n;i++)
- {
- System.out.println(i + " -> " + adjacencyList.get(i));
- }
- }
- public static void main(String[] args) throws IOException
- {
- read("in.txt");
- solve();
- PrintWriter pr = new PrintWriter(new File("out.txt"));
- if(node != -1)
- {
- pr.print(diam + "\n");
- pr.print(node + 1);
- }
- else
- {
- pr.print("impossible");
- }
- pr.flush();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement