当前位置:首页 > 开发 > 编程语言 > Java > 正文

求一个无向图的最大环的边数(POJ3895) (java解答)

发表于: 2012-11-08   作者:128kj   来源:转载   浏览:
摘要: POJ 3895 题意:    求最大环的边数,给出一个无向图,图中每条边的长度都是1,求图中最长环的长度是多少? 样例: Sample Input 1 -------->这里是测试次数 7 8 ----------------->七个点,八条边 3 4 ---------------->顶点3到4有一条边 1 4 1 3 7 1
POJ 3895
题意:
   求最大环的边数,给出一个无向图,图中每条边的长度都是1,求图中最长环的长度是多少?

样例:
Sample Input

1 -------->这里是测试次数
7 8 ----------------->七个点,八条边
3 4 ---------------->顶点3到4有一条边
1 4
1 3
7 1
2 7
7 5
5 6
6 2

Sample Output

4

AC代码:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.List;
public class Main {
	private int n;//顶点个数
          private boolean[] used;//节点状态,值为false的是未访问的   
          private List< ArrayList< Integer>> G;//邻接表
          private int maxlen=0;//最大环的长度
          private int[] num;//记录搜索到某顶点时已搜索过的顶点数
  

        public Main(int n,List< ArrayList< Integer>> G){
             this.n=n;
             this.G=G;
             used=new boolean[n+1];  
             num=new int[n+1];
        }


private void dfs(int v, int t)  {  
   
    num[v] = t;  //搜索到v时,已搜索过的顶点数
    used[v] = true;  
    int x = G.get(v).size();  
    for(int i = 0; i < x; i++){ //对V的每一个邻接点 
        if(!used[G.get(v).get(i)]){ //没有发现环 
            dfs(G.get(v).get(i), t + 1);  
        }  
        else  //发现环,更新最大环的边数
        {  
            if(maxlen < num[v] - num[G.get(v).get(i)] + 1)  
            maxlen = num[v] - num[G.get(v).get(i)] + 1;  
        }  
    }  
  }  
   public void go(){
      for(int i = 1; i <= n; i++){ //遍历每一个顶点
            if(!used[i])  
            dfs(i, 1);  //深度优先搜索
        }  
        if(maxlen > 2) System.out.printf("%d\n", maxlen);  
        else System.out.println("0");  
  }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t=sc.nextInt();
        while(t-->0){
            int n=sc.nextInt();
            int m=sc.nextInt();
             
            List< ArrayList< Integer>> G;
            G = new ArrayList< ArrayList< Integer>>();//初始化邻接表
            for(int i = 1;i<=n+1;i++)
                  G.add(new ArrayList< Integer>());
            for(int i=0;i<m;i++){
              int u = sc.nextInt();
              int v = sc.nextInt();
              G.get(u).add(v);
              G.get(v).add(u);      
             }
              
            Main ma=new Main(n,G);
             ma.go();
          
        }
   }
}

源码:

求一个无向图的最大环的边数(POJ3895) (java解答)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
问题描述如下: 具体代码实现: 1 #include<stdlib.h> 2 #include<stdio.h> 3 #define
// 无向图的一节点到另一节点的最短路径(边数最少的路径)(采用邻接表存储).cpp : Defines the e
// 无向图的一节点到另一节点的最短路径(边数最少的路径)(采用邻接表存储).cpp : Defines the e
// 无向图的一节点到另一节点的最短路径(边数最少的路径)(采用邻接表存储).cpp : Defines the e
osg场景图是一个有向无循环图,如下图所示: osg场景图中,所有节点全部为osg::Node或从其派生出来
当每个任务有前后置关系时,需要找到一种满足前后置关系的路线,将任务完成。 如果将每个任务看成一
POJ1734 题意:给定一个N个点的无向图,求一个最小环(各边权值和最小的环)并输出路径。 样例: Sample
http://www.cnblogs.com/en-heng/p/4002658.html 求无 向连通图的割点 割点与连通度 在无向连通图中
转自:http://blog.sina.com.cn/s/blog_8f06da990101252l.html Green Hackenbush Hackenbush游戏是通
转自:http://blog.sina.com.cn/s/blog_8f06da990101252l.html Green Hackenbush <span style="fo
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号