文章目录

• 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<n; ++i){
            if(!visited[i] && g[index][i] == 1){
                dfs(i);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        sc.nextToken();
        n = (int)sc.nval + 1;
        sc.nextToken();
        int m = (int)sc.nval;
        sc.nextToken();
        int k = (int)sc.nval;
        g = new int[n][n];
        visited = new boolean[n];
        for (int i = 0; i < m; i++) {
            sc.nextToken();
            int x = (int)sc.nval;
            sc.nextToken();
            int y = (int)sc.nval;
            g[x][y] = 1;
            g[y][x] = 1;
        }
        for (int i = 0; i < k; i++) {
            Arrays.fill(visited, false);
            sc.nextToken();
            int z = (int)sc.nval;
            visited[z] = true;
            int count = 0;
            for (int j = 1; j < n; j++) {
                if(!visited[j]){
                    count++;
                    dfs(j);
                }
            }
            System.out.println(count-1);
        }
    }
}