1. 公交路线
    给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。

例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。

求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。

示例 1：

输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出：2
解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。
示例 2：

输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
输出：-1

解题思路
边界条件
如果原本起点和终点一致，则不用坐车
如果没有公交车，则不可达
如果起点和终点在同一条公交线路上，则坐一次公交就可以
先初始化并查集（但是需要以公交路线为图中的点）
然后再利用BFS进行搜索查找，知道起点和终点所在的公交路线有交集
图片说明 

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if(source == target) return 0;
        if(routes==null || routes.length==0 ) return -1;
        List<Integer> before=new ArrayList<>();//记录出现source的公交车线路
        List<Integer> after=new ArrayList<>();//记录出现target的公交车线路
        int n=routes.length;
        for(int i=0;i<n;i++){
            Arrays.sort(routes[i]);//先将公交车的站点排序，便于之后查找
            if(contains(routes[i],source)) before.add(i);
            if(contains(routes[i],target)) after.add(i);
        }
        //如果before和after在一趟路线则直接返回1
        for(int i:before){
            if(after.contains(i)) return 1;
        }
        //记录和当前公交路线有交集的公交路线
        HashMap<Integer,List<Integer>> routeMap=new HashMap<>();
        boolean[] visited=new boolean[n];
        //初始化routeMap
        for(int i=0;i<n;i++){
            visited[i]=false;
            routeMap.put(i,new ArrayList<Integer>());
        }
        //更新routeMap
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(hasCommon(routes[i],routes[j])){
                    routeMap.get(i).add(j);
                    routeMap.get(j).add(i);
                }
            }
        }
        // 更新出发点使用线路信息 并 判断
        boolean hasReached = false;//此时未到达
        int count = 1;//先上车
        while(!hasReached){
            count++;//换乘下辆车
            List<Integer> newbefore=new ArrayList<>();
            //针对before中的每条公交线路
            for(int beforeItem:before){
                //遍历它可以到达的所有公交线路（有交集）
                for(int routeItem:routeMap.get(beforeItem)){
                    //如果已经在上一个集合或者当前集合，则跳过
                    if(newbefore.contains(routeItem) || before.contains(routeItem)) continue;
                    //如果已经访问过，则继续
                    if(visited[routeItem]) continue;
                    //将该公交路线作为新的起点
                    newbefore.add(routeItem);
                    visited[routeItem]=true;
                }
            }
            //证明不可继续前进
            if(newbefore.size()==0) break;
            //更新起点集合
            before=newbefore;
            //判断是否可达
            for(int i:before){
                if(after.contains(i)) hasReached=true;
            }
        }

        return hasReached?count:-1;
    }
    //A和B都是有序数组
    public boolean hasCommon(int[] A,int[] B){
        int i=0,j=0;
        while(i<A.length && j<B.length){
            if(A[i]==B[j]) return true;
            if(A[i]>B[j]) j++;
            else i++;
        }
        return false;
    }
    public boolean contains(int[] route,int key){//二分查找判断公交路线是否含有某个站
        int left=0;
        int right=route.length-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(key == route[mid]) return true;
            if(key > route[mid]) left=mid+1;
            if(key < route[mid]) right=mid-1;
        }
        return false;
    }
}