PAT 甲级 1013 Battle Over Cities (25 分)（Java）

• PAT 甲级 1013 Battle Over Cities (25 分)（Java）
• • 题目
  • 大体题意
  • 解题思路
  • 解法
  • • 解法一

题目链接

给定一个无向连通图，然后去掉其中某个点，问是否还连通，如果不连通，需要最少几条路使其连通；

1. 通过二维数组构建无向连通图；
2. 通过一维数组标识当前点是否可用以及是否访问过；
3. 通过深搜判定当前是否是连通图，否，则记录有几个连通分量，使其连通的最少路即连通分量减一；

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Main {

    static int[][] g;
    static boolean[] visited;
    static int n;

    public static void dfs(int index){
        visited[index] = true;
        for(int i=1; i