复习版

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define not !
#define and &&
#define or ||

#define ri register int
#define rep(inc, frm, to) for (ri inc = frm; inc < (to); ++inc)
#define rep2(inc, frm, to) for (ri inc = frm; inc > (to); --inc)

#define setbit(x, y) x |= 1 << y
#define clrbit(x, y) x &= ~(1 << y)
#define getbit(x, y) x >> y & 1
#define flipbit(x, y) x ^= 1 << y
#define show_bin(x) { rep2(i, 31, ~0) printf("%d%c", getbit(x, i), i ? 9 : 10); }

#define min(a, b) (a < b ? a : b)
#define max(a, b) (a > b ? a : b)

#define SWAP(a, b) { typeof(a) tmp = a; a = b; b = tmp; }

typedef long long int ll;
#define r() fast_read()

int is_digit(const char c) {
  return c >= 48 and c <= 57;
}

ll fast_read(void) {
  ll n = 0, sign = 1;
  char c = getchar();
  while (not is_digit(c)) {
    if (c == '-') sign = ~0;
    c = getchar();
  }
  while (is_digit(c)) {
    n = (n << 1) + (n << 3) + (c ^ 48);
    c = getchar();
  }
  return sign * n;
}

#define MAX_N 1010
int head[MAX_N], edge_cnt;
typedef struct Edge Edge;
struct Edge {
  int to, nxt;
} edges[MAX_N * MAX_N];

void addEdge(int u, int v) {
  edges[++edge_cnt] = (Edge) {v, head[u]};
  head[u] = edge_cnt;
}

int n, m, k;
bool C[MAX_N][MAX_N], seen[MAX_N];

void DFS(int u, int removed) {
  seen[u] = 1;
  for (int e = head[u], v; e; e = edges[e].nxt) {
    v = edges[e].to;
    if (v == removed or seen[v]) continue;
    DFS(v, removed);
  }
}

signed main(int argc, char const *argv[]) {

  // freopen("test.in", "r", stdin);

  n = r(), m = r(), k = r();
  for (int u, v; m--;) {
    u = r(), v = r();
    addEdge(u, v), addEdge(v, u);
  }

  // print_adj();
  for (int x; k--;) {
    x = r();
    int ccs = 0;
    memset(seen, false, sizeof seen);
    rep(u, 1, n + 1) {
      if (u == x or seen[u]) continue;
      ++ccs, DFS(u, x);
    }

    printf("%d\n", ccs - 1);
  }

  // fclose(stdin);
  return ~~(0 ^ 0);
}

算法1： DFS

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n, m, k, u, v;

void dfs(vector<vector<int>>& g, vector<int>& seen, int cur) {
  if (seen[cur]++) return;
  for (const auto& nxt : g[cur]) dfs(g, seen, nxt);
}

int main(void) {
  scanf("%d %d %d", &n, &m, &k);
  vector<vector<int>> graph(n + 1);
  // build the undirected graph!
  while (m--) {
    scanf("%d %d", &u, &v);
    graph[u].emplace_back(v);
    graph[v].emplace_back(u);
  }

  vector<int> cities(k);
  for (int i = 0; i < k; ++i) cin >> cities[i];

  // reconstruct the graph (delete a city)
  for (const auto& city : cities) {
    vector<vector<int>> g(graph); // clone
    for (const int nei : g[city])
      g[nei].erase(find(begin(g[nei]), end(g[nei]), city));
    g[city].clear();

    int ccs = 0; // the number of the connected components!!!
    vector<int> seen(n + 1);
    for (int i = 1; i <= n; ++i) {
      if (i == city || seen[i]) continue;
      dfs(g, seen, i);
      ++ccs;
    }
    printf("%d\n", ccs - 1);
  }
}

TODO： 算法2： Disjoint Set!