1013 Battle Over Cities

• dfs确定连通块数量

const int N = 1e6 + 10, M = 2 * N, INF = 0x3f3f3f3f;
int n, m, k, h[N], e[M], ne[M], idx = 0;
bool visited[N];
void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}void dfs(int u, int x)
{visited[u] = true;for(int v = h[u]; v != -1; v = ne[v]){int j = e[v];if(visited[j] == false){dfs(j, x);}}
}int find_repaired_highways(int x)
{fill(visited, visited + N, false);int cnt = 0;visited[x] = true;for(int i = 1; i <= n; ++i){if(visited[i] == false){dfs(i, x);cnt++;}}return cnt - 1;
}int main()
{fill(h, h + N, -1);cin >> n >> m >> k;while(m--){int a, b;cin >> a >> b;add(a, b);add(b, a);}while(k--){int x;cin >> x;int ret = find_repaired_highways(x);cout << ret << endl;}return 0;
}