解法一：深度优先搜索

题目大意抽象：图中删除某个点和相关的边，求使得图连通所需要添加的最少边数。
使得图连通所需要添加的最少边数 = 独立连通分支数量 - 1
可以使用深度优先搜索的方法来计算独立连通分支的数量。

import java.io.*;
import java.util.*;
public class Main {
    private static boolean[][] map;
    private static boolean[] isVisited;
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        int N = (int) in.nval;
        in.nextToken();
        int M = (int) in.nval;
        in.nextToken();
        int K = (int) in.nval;
        map = new boolean[N + 1][N + 1];
        for (int i = 0, u, v; i < M; ++i) {
            in.nextToken();
            u = (int) in.nval;
            in.nextToken();
            v = (int) in.nval;
            map[u][v] = map[v][u] = true;
        }
        for (int i = 0, city, ans; i < K; ++i) {
            isVisited = new boolean[N + 1];
            ans = 0;
            in.nextToken();
            city = (int) in.nval;
            isVisited[city] = true;
            for (int index = 1; index <= N; ++index) {
                if (!isVisited[index]) {
                    ++ans;
                    dfs(index);
                }
            }
            // 连通所需的路径数量 = 独立联通分支数量 - 1
            out.println(ans - 1);
        }
        out.flush();
    }
    private static void dfs(int city) {
        isVisited[city] = true;
        for (int i = 1; i < map.length; ++i) {
            if (map[city][i] && !isVisited[i]) {
                dfs(i);
            }
        }
    }
}

解法二：并查集

也可以用并查集来统计独立连通分支数量，不过Java写的话最后一个测试点超时了😅。

import java.io.*;
import java.util.*;
public class Main {
    private static int[] father;
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        int N = (int) in.nval;
        in.nextToken();
        int M = (int) in.nval;
        in.nextToken();
        int K = (int) in.nval;
        int[][] edges = new int[M][2];
        for (int i = 0; i < M; ++i) {
            in.nextToken();
            edges[i][0] = (int) in.nval;
            in.nextToken();
            edges[i][1] = (int) in.nval;
        }
        for (int i = 0, city, ans; i < K; ++i) {
            father = new int[N + 1];
            for (int index = 1; index <= N; ++index) {
                father[index] = index;
            }
            ans = 0;
            in.nextToken();
            city = (int) in.nval;
            for (int[] edge : edges) {
                // 合并分支
                if ((edge[0] != city) && (edge[1] != city)) {
                    union(edge[0], edge[1]);
                }
            }
            for (int index = 1; index <= N; ++index) {
                if (index == father[index]) {
                    ++ans;
                }
            }
            // ans为包括city在内的独立连通分支数量
            out.println(ans - 2);
        }
        out.flush();
    }
    private static int find(int x) {
        if (x == father[x]) {
            return x;
        }
        father[x] = find(father[x]);
        return father[x];
    }
    private static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            father[a] = b;
        }
    }
}