蓝桥杯-危险系数

危险系数

import java.util.ArrayList;  
import java.util.List;  
import java.util.Scanner;  
  
public class 危险系数 {  
  
    public static void main(String[] args) {  
        // TODO Auto-generated method stub  
        Scanner scanner = new Scanner(System.in);  
        int n = scanner.nextInt();  
        int m = scanner.nextInt();  
        TuNode[] tuNodes = new TuNode[n];  
        List<TuNode> geDian=new ArrayList<TuNode>();  
        int i;  
        for (i = 0; i < n; i++) {  
            tuNodes[i] = new TuNode(i + 1);  
            geDian.add(tuNodes[i]);  
        }  
        int x;  
        int y;  
        for (i = 0; i < m; i++) {  
            x = scanner.nextInt();  
            y = scanner.nextInt();  
            tuNodes[x - 1].jiedian.add(tuNodes[y - 1]);  
            tuNodes[y - 1].jiedian.add(tuNodes[x - 1]);  
        }  
        int qiDian=scanner.nextInt();  
        int zhongDian=scanner.nextInt();  
        List<TuNode> jiHe = new ArrayList<TuNode>();  
        jiHe.add(tuNodes[qiDian-1]);  
          
        List<TuNode> list =search(tuNodes[qiDian-1], tuNodes[zhongDian-1], jiHe,geDian);  
  
        if (list.size() == 0) {  
            System.out.println("-1");  
        } else {  
            System.out.print(geDian.size()-2);  
        }  
    }  
  
    public static List<TuNode> search(TuNode qiDian, TuNode zhongDian,  
            List<TuNode> jiHe,List<TuNode> geDian) {  
        int i;  
  
        List<TuNode> listTemp1;  
  
        List<TuNode> listTemp2 = new ArrayList<TuNode>();  
  
        List<TuNode> listTemp3 = new ArrayList<TuNode>();  
  
        for (i = 0; i < qiDian.jiedian.size(); i++) {  
  
            // 将jiHe中的元素赋给listTemp1  
            listTemp1 = new ArrayList<TuNode>(jiHe);  
  
            // listTemp2中添加当前循环元素  
            listTemp2.add(qiDian.jiedian.get(i));  
  
            // 对listTemp2取listTemp1的交集  
            listTemp2.retainAll(listTemp1);  
  
  
            if (qiDian.jiedian.get(i).value == zhongDian.value) {  
  
                listTemp1.add(qiDian.jiedian.get(i));  
                geDian.retainAll(listTemp1);  
                  
                return listTemp1;  
            } else if (listTemp2.size() == 0) {  
  
                listTemp1.add(qiDian.jiedian.get(i));  
  
                List<TuNode> listTemp4 = new ArrayList<TuNode>(listTemp1);  
  
                List<TuNode> listTemp5 = search(qiDian.jiedian.get(i),  
                        zhongDian, listTemp4,geDian);  
                if (listTemp3.size() != 0) {  
                    if (listTemp5.size() < listTemp3.size()  
                            && listTemp5.size() != 0) {  
                        listTemp3 = new ArrayList<TuNode>(listTemp5);  
                    }  
                } else {  
                    listTemp3 = new ArrayList<TuNode>(listTemp5);  
                }  
            }  
            listTemp2.clear();  
        }  
        return listTemp3;  
    }  
}  
  
class TuNode {  
    int value;  
    List<TuNode> jiedian = new ArrayList<TuNode>();  
  
    public TuNode(int value) {  
        // TODO Auto-generated constructor stub  
        this.value = value;  
    }  
}