It is vitally important to have all the cities connected by highways in a war. If a city is occupied by the enemy, all the highways from/toward that city are closed. We must know immediately if we need to repair any other highways to keep the rest of the cities connected. Given the map of cities which have all the remaining highways marked, you are supposed to tell the number of highways need to be repaired, quickly. For example, if we have 3 cities and 2 highways connecting city1-city2 and city1-city3. Then if city1 is occupied by the enemy, we must have 1 highway repaired, that is the highway city2-city3.
翻译：在战争中，所有的城市都要用公路连接起来，这一点至关重要。如果一个城市被敌人占领，所有进出该城市的公路都将关闭。我们必须立即知道如果我们需要修复任何其他高速公路，以保证其余城市的连通。在地图上标出了所有剩下的高速公路，你应该告诉他们需要修复的高速公路的数量。 比如我们有三个城市和两条公路分别连接城市1和城市2，城市1和城市3.如果城市1被敌人攻占，我们必须修复一条路，那就是城市2到城市3的路
Each input file contains one test case. Each case starts with a line containing 3 numbers N (<1000), M and K, which are the total number of cities, the number of remaining highways, and the number of cities to be checked, respectively. Then M lines follow, each describes a highway by 2 integers, which are the numbers of the cities the highway connects. The cities are numbered from 1 to N. Finally there is a line containing K numbers, which represent the cities we concern.
翻译：每个输入文件包含一个测试用例。每个样例都以包含3个数字N（<1000）、M和K的一行开始，分别是城市数、剩余公路数量和待检查城市数量。接着是M行，每行用2个整数来描述一条公路，这是公路连接的城市的数目。城市从1到N编号。最后有一行包含K个数字，代表我们关心的城市。
For each of the K cities, output in a line the number of highways need to be repaired if that city is lost.
翻译：对于K个城市中的每一个，在一行输出如果该失去该城市，需要修复的高速公路数量。
3 2 3 1 2 1 3 1 2 3
1 0 0
题目大意就是当删去一个结点以及与之连接的所有边后，要增加多少边才能让剩下的图是连通图。假设删去一个点和它连接的所有边后的图不再是连通图且分为3个连通块b1、b2、b3，则只要b1与b2之间加一条边，b2和b3之间加一条边即可，也就是说需要添加的边数等于连通块个数减1。现在问题就转化为了求无向图的连通图个数，在数据结构中学过此时可以用DFS解决。 每次访问一个连通块并将块内所有顶点都标记为已访问，接着再访问下一个连通块，因此只要在访问过程中计数遍历的连通块的个数即可
#include <iostream> #include <map> #include <vector> #include <climits> #include <string.h> using namespace std; vector<int> G[1000]; bool visit[1000]; int n, m, k; int del_point; void dfs(int); void dfs_trav(); int main() { cin >> n >> m >> k; for (int i = 0; i < m; i++) { int one, two; cin >> one >> two; G[one].push_back(two); G[two].push_back(one); } for (int i = 0; i < k; i++) { cin >> del_point; //要删去的点 memset(visit, false, sizeof(visit)); //初始化访问数组 dfs_trav(); } system("pause"); return 0; } void dfs_trav() { int block = 0; //记录连通块数 for (int j = 1; j <= n; j++) { if (j != del_point && visit[j] == false) //未被删除且未被访问 { dfs(j); block++; } } cout << block - 1 << endl; } void dfs(int v) { if (v == del_point) //遍历到已删除结点时返回 return; visit[v] = true; //标为已访问 for (int i = 0; i < G[v].size(); i++) if (visit[G[v][i]] == false) dfs(G[v][i]); }