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();
}
}
}
源码:
分享到:
相关推荐
用java的biginteger实现的poj1001,比较简单的方法
POJ 1328 java做!雷达问题!java版本!AC答案~
这道题的目的是求如去除某个点,能把图分成多少个子图,求这样子图的最大数。 其实就是求割点,然后看每个割点能把图分成多少个子图,当然原图不一定是连通的。 割点的求法各个书籍上都有,其实就是用DFS进行遍历。
NULL 博文链接:https://128kj.iteye.com/blog/1705139
POJ1048,加强版的约瑟夫问题 难度中等
poj平台有关数据结构题的Java源码 1159 1276 2406 2502 2509 2513 2533 2778 3176
北大poj JAVA源码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ 1300 Door Man:无向图、欧拉定理、gets、sscanf
北大POJ2002-Squares 解题报告+AC代码
1、前序遍历的第一个字母必是 根 2、在中序遍历的字母串中找出 根字母,那么根字母左右两边的字符串就分别是它的左、右子树 3、利用递归复原二叉树(把子树看作新的二叉树) 4、后序遍历特征:后序遍历字母串 自右至...
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
NULL 博文链接:https://128kj.iteye.com/blog/1749213
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
对于POJ1852题目和详细的解答,代码已经通过
NULL 博文链接:https://128kj.iteye.com/blog/1744222
poj1002 的源代码 第一次做 超时了
pku acm 第3356题 AGTC Java代码,有详细的注释,动态规划
acm pku poj 1000 1001 1002 1003 1201