1013 Battle Over Cities (25分)
连通图去除某个顶点，需要加几条路径使其再次连通
思路
连通图去除某个顶点 --> 变成k个连通分量 --> k个连通分量需要增加k-1条路线使其再次连通即：求出去掉顶点后，求出图的连通分量数即可知识点
dfs查找连通分量数k个连通分量需要增加k-1条路线使其再次连通fill(visited, visited + 1000, false);cin / cout 会超时，换成scanf / printf //参考柳神 //#define _CRT_SECURE_NO_WARNINGS #include<iostream> int edge[1000][1000];//图 bool visited[1000];//是否访问过 int n;//n - number of cities void dfs(int v) { visited[v] = true;//已访问 for (int i = 1; i <= n; i++) { if (visited[i] == false && edge[v][i] == 1)//未访问且有边 dfs(i); } } int main() { //freopen("input.txt","r", stdin); int m, k; //m - the number of remaining highways //k - the number of cities to be checked int a, b; //edge scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < m; i++) { scanf("%d%d", &a, &b); edge[a][b] = edge[b][a] = 1; } for (int i = 0; i < k; i++) { std::fill(visited, visited + 1000, false);//初始化 scanf("%d", &a); int cnt = 0; visited[a] = true;//去掉a for (int j = 1; j <= n; j++) if (visited[j] == false) { dfs(j);//深度优先查找连通分量数 cnt++; } printf("%d\n", cnt -1); } return 0; }