Submission #140770

---

Source Code Expand

import java.util.*;

public class Main {
  public static void main(String args[]) {
    Scanner in = new Scanner(System.in);
    ArrayList<ArrayList<Integer>> g1 = readGraph(in);
    ArrayList<ArrayList<Integer>> g2 = readGraph(in);
    int[] d1 = dist(g1);
    int[] d2 = dist(g2);
    int rMax1 = d1[0];
    int rMin1 = d1[0];
    for( int d : d1 ) {
      rMax1 = Math.max(rMax1,d);
      rMin1 = Math.min(rMin1,d);
    }
    int rMax2 = d2[0];
    int rMin2 = d2[0];
    for( int d : d2 ) {
      rMax2 = Math.max(rMax2,d);
      rMin2 = Math.min(rMin2,d);
    }
    int rMin = Math.max (Math.max(rMax1,rMax2),rMin1 + rMin2 + 1);
    int rMax = rMax1 + rMax2 + 1;
    System.out.println(rMin + " " + rMax);
  }

  public static ArrayList<ArrayList<Integer>> readGraph(Scanner in) {
    int n = in.nextInt();
    int m = in.nextInt();
    ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>();
    for( int i = 0; i < n; i++ ) 
      g.add(new ArrayList<Integer>());
    for( int i = 0; i < m; i++ ) {
      int u = in.nextInt();
      int v = in.nextInt();
      g.get(u).add(v);
      g.get(v).add(u);
    }
    return g;
  }

  public static int[] dist(ArrayList<ArrayList<Integer>> g) {
    int[] d = new int[g.size()];
    boolean[] vis = new boolean[g.size()];
    Queue<Pair> queue = new LinkedList<Pair>();
    for( int i = 0; i < g.size(); i++ ) {
      Arrays.fill(vis,true);
      queue.add(new Pair(i,0));
      vis[i] = false;
      int max = 0;
      //System.out.println("start: "+ i);
      while (!queue.isEmpty()) {
        Pair p = queue.poll();
        for( int u : g.get(p.first) ) {
          if( vis[u] ) {
            vis[u] = false;
            queue.offer(new Pair(u,p.second+1));
            max = p.second+1;
            //System.out.println("v: " + u + " d: " +(p.second+1));
          }
        }
      }
      d[i] = max;
    }
    return d;
  }
  static class Pair {
    int first;
    int second;
    public Pair(int f,int s) {
      this.first = f;
      this.second = s;
    }
  }
}

Submission Info

Judge Result