POJ 3895 Cycles of Lanes

 1 import java.util.ArrayList;
 2 import java.util.Arrays;
 3 import java.util.Scanner;
 4 import java.util.List;
 5 public class Main {
 6     private int n;//顶点个数
 7         private boolean[] used;//节点状态,值为false的是未访问的   
 8     private List< ArrayList< Integer>> G;//邻接表
 9     private int maxlen=0;//最小环的长度
10         private int[] num;//记录搜索到某顶点时已搜索过的顶点数
11   
12 
13         public Main(int n,List< ArrayList< Integer>> G){
14              this.n=n;
15              this.G=G;
16              used=new boolean[n+1];  
17              num=new int[n+1];
18         }
19 
20 
21 private void dfs(int v, int t)  {  
22    
23     num[v] = t;  //搜索到v时,已搜索过的顶点数
24     used[v] = true;  
25     int x = G.get(v).size();  
26     for(int i = 0; i < x; i++){ //对V的每一个邻接点 
27         if(!used[G.get(v).get(i)]){ //没有发现环 
28             dfs(G.get(v).get(i), t + 1);  
29         }  
30         else  //发现环
31         {  
32             if(maxlen < num[v] - num[G.get(v).get(i)] + 1)  
33             maxlen = num[v] - num[G.get(v).get(i)] + 1;  
34         }  
35     }  
36   }  
37    public void go(){
38       for(int i = 1; i <= n; i++){ //遍历每一个顶点
39             if(!used[i])  
40             dfs(i, 1);  //深度优先搜索
41         }  
42         if(maxlen > 2) System.out.printf("%d\n", maxlen);  
43         else System.out.println("0");  
44   }
45 
46     public static void main(String[] args) {
47         Scanner sc = new Scanner(System.in);
48         int t=sc.nextInt();
49         while(t-->0){
50             int n=sc.nextInt();
51             int m=sc.nextInt();
52              
53             List< ArrayList< Integer>> G;
54             G = new ArrayList< ArrayList< Integer>>();//初始化邻接表
55             for(int i = 1;i<=n+1;i++)
56                   G.add(new ArrayList< Integer>());
57             for(int i=0;i<m;i++){
58               int u = sc.nextInt();
59               int v = sc.nextInt();
60               G.get(u).add(v);
61               G.get(v).add(u);      
62              }
63               
64             Main ma=new Main(n,G);
65              ma.go();
66           
67         }
68    }
69 }