抗日战争Java_算法笔记_188:历届试题危险系数(Java)

た入场券 2022-11-10 05:25 160阅读 0赞

importjava.util.ArrayList;importjava.util.Scanner;public classMain \{public static intn, m;public static intcount;public static int\[\] DFN;public static int\[\] Low;public static int\[\] parent;public static ArrayList\[\] list;public static ArrayListpoint;

@SuppressWarnings("unchecked")public voidinit() \{

count= 0;

DFN= new int\[n + 1\];

Low= new int\[n + 1\];

parent= new int\[n + 1\];

list= new ArrayList\[n + 1\];

point= new ArrayList();for(int i = 1;i <= n;i++)

list\[i\]= new ArrayList();

\}public void TarJan(int start, intfather) \{

DFN\[start\]= ++count;

Low\[start\]=DFN\[start\];

parent\[start\]=father;int childern = 0;for(int i = 0;i < list\[start\].size();i++) \{int j =list\[start\].get(i);if(DFN\[j\] == 0) \{

childern++;

TarJan(j, start);

Low\[start\]=Math.min(Low\[start\], Low\[j\]);if(parent\[start\] == -1 && childern > 1) \{if(!point.contains(start))

point.add(start);

\}if(parent\[start\] != -1 && Low\[j\] >=DFN\[start\]) \{if(!point.contains(start))

point.add(start);

\}else if(j !=parent\[start\]) \{

Low\[start\]=Math.min(Low\[start\], DFN\[j\]);

\}public void dfs(int a, boolean\[\] visited) \{

visited\[a\]= true;for(int i = 0;i < list\[a\].size();i++) \{int j =list\[a\].get(i);if(visited\[j\] == false)

dfs(j, visited);

\}public void getResult(int a, intb) \{

TarJan(1, -1);int result = 0;for(int i = 0;i < point.size();i++) \{if(point.get(i) == a || point.get(i) ==b)continue;else\{boolean\[\] visited = new boolean\[n + 1\];

visited\[point.get(i)\]= true;

dfs(a, visited);if(visited\[b\] == false) \{

result++;

System.out.println(result);

\}public static voidmain(String\[\] args) \{

Main test= newMain();

Scanner in= newScanner(System.in);

n=in.nextInt();

m=in.nextInt();

test.init();for(int i = 1;i <= m;i++) \{int u =in.nextInt();int v =in.nextInt();

list\[u\].add(v);

list\[v\].add(u);