Java教程

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

本文主要是介绍PAT 甲级 1013 Battle Over Cities (25 分)(Java),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

  • 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);
        }
    }
}

这篇关于PAT 甲级 1013 Battle Over Cities (25 分)(Java)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!