問(wèn)題描述
X 國(guó)的一個(gè)網(wǎng)絡(luò)使用若干條線(xiàn)路連接若干個(gè)節(jié)點(diǎn)。節(jié)點(diǎn)間的通信是雙向的。某重要數(shù)據(jù)包，為了安全起見(jiàn)，必須恰好被轉(zhuǎn)發(fā)兩次到達(dá)目的地。該包可能在任意一個(gè)節(jié)點(diǎn)產(chǎn)生，我們需要知道該網(wǎng)絡(luò)中一共有多少種不同的轉(zhuǎn)發(fā)路徑。

源地址和目標(biāo)地址可以相同，但中間節(jié)點(diǎn)必須不同。

如下圖所示的網(wǎng)絡(luò)。

網(wǎng)絡(luò)

1 -> 2 -> 3 -> 1 是允許的

1 -> 2 -> 1 -> 2 或者 1 -> 2 -> 3 -> 2 都是非法的。

輸入格式
輸入數(shù)據(jù)的第一行為兩個(gè)整數(shù)N M，分別表示節(jié)點(diǎn)個(gè)數(shù)和連接線(xiàn)路的條數(shù)(1<=N<=10000; 0<=M<=100000)。

接下去有M行，每行為兩個(gè)整數(shù) u 和 v，表示節(jié)點(diǎn)u 和 v 聯(lián)通(1<=u,v<=N , u!=v)。

輸入數(shù)據(jù)保證任意兩點(diǎn)最多只有一條邊連接，并且沒(méi)有自己連自己的邊，即不存在重邊和自環(huán)。

輸出格式
輸出一個(gè)整數(shù)，表示滿(mǎn)足要求的路徑條數(shù)。
樣例輸入1
3 3
1 2
2 3
1 3
樣例輸出1
6
樣例輸入2
4 4
1 2
2 3
3 1
1 4
樣例輸出2
10

import java.util.ArrayList;  
import java.util.List;  
import java.util.Scanner;  
  
public class 網(wǎng)格尋路 {  
  
    public static int sum=0;  
      
    public static void main(String[] args) {  
        // TODO Auto-generated method stub  
        Scanner scanner=new Scanner(System.in);  
        int i,qiDian,zhongDian;  
        List<WangNode> jiHe;  
          
        int nodeShu=scanner.nextInt();  
        int bianShu=scanner.nextInt();  
        WangNode[] wangNodes=new WangNode[nodeShu];  
          
        for(i=0;i<nodeShu;i++){  
            wangNodes[i]=new WangNode(i+1);  
        }  
          
        for(i=0;i<bianShu;i++){  
            qiDian=scanner.nextInt()-1;  
            zhongDian=scanner.nextInt()-1;  
            wangNodes[qiDian].jieDian.add(wangNodes[zhongDian]);  
            wangNodes[zhongDian].jieDian.add(wangNodes[qiDian]);  
        }  
        for(i=0;i<nodeShu;i++){  
            jiHe=new ArrayList<WangNode>();  
            jiHe.add(wangNodes[i]);  
            search(wangNodes[i],jiHe);  
            jiHe.clear();  
        }  
        System.out.println(sum);  
    }  
      
    public static void search(WangNode qiDian,List<WangNode> jiHe){  
        List<WangNode> jiHeTemp=new ArrayList<WangNode>(jiHe);  
        WangNode lastNode;  
        try {  
            lastNode = jiHe.get(jiHeTemp.size()-2);  
        } catch (Exception e) {  
            lastNode=null;  
        }  
        int i;  
        for(i=0;i<qiDian.jieDian.size();i++){  
            if(!qiDian.jieDian.get(i).equals(lastNode)){  
                jiHeTemp.add(qiDian.jieDian.get(i));  
                if(jiHeTemp.size()==4){  
                    sum+=1;  
                    for(WangNode wangNode:jiHeTemp){  
                        System.out.print(wangNode.value+" ");  
                    }  
                    System.out.println();  
                }else{  
                    search(qiDian.jieDian.get(i),jiHeTemp);  
                }  
                jiHeTemp.remove(jiHeTemp.size()-1);  
            }  
        }  
    }  
}  
  
class WangNode{  
    int value;  
    List<WangNode> jieDian=new ArrayList<WangNode>();  
    public WangNode(int value) {  
        // TODO Auto-generated constructor stub  
        this.value=value;  
    }  
} 

5條測(cè)試，其中有一條超時(shí)，我知道超時(shí)問(wèn)題所在，但是不知道如何去解決，例如1-2-3-4有了就不必再尋找4-3-2-1，但是不知道怎么去解決