[PAT A1013]Battle Over Cities
题目描述
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 city?1??-city?2?? and city?1??-city?3??. Then if city?1?? is occupied by the enemy, we must have 1 highway repaired, that is the highway city?2??-city?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.
输出格式
For each of the K cities, output in a line the number of highways need to be repaired if that city is lost.
输入样例
3 2 3
1 2
1 3
1 2 3输出样例
1
0
0解析
1.题目大意：输入n,m,k三个数，n表示城市的个数（默认编号1~N）,m表示边数（无向边），k表示要查询的城市数。然后m行输入边的两个顶点，最后一行输入K个检查的城市结点。对于每个输入的城市，表示该城市被敌军占领，切断所有该城市与其它城市的路径，要求需要新建多少条路径，才能使得除了该城市以外的城市之间能够畅通无阻地联系。
2.我的思路是，即判断除去该结点后，连通分量的个数，假如有3个分量，由于他们内部是连通的，所以只需要建2条路径，使得这3个连通分量能够连接起来即可满足条件。
3.由于是刚接触图的题目，写题还是很生疏，诸多繁杂，还望看官耐心看看：
#include<iostream>
using namespace std;
const int maxn = 1010;
int n, m, k;
int cnt = 0; //记录连通分量的个数
bool Graph[maxn][maxn]; //记录初始图（备份）
bool Graph1[maxn][maxn]; //记录修改之后的图（每次查找城市K都不一样）
bool visit[maxn] = { false }; //某个结点有没有被访问过
void init();
void DFS(int id);
void DFSTraverse();
int main()
{scanf("%d %d %d", &n, &m, &k);for (int i = 0; i < m; i++) {int id1, id2;scanf("%d %d", &id1, &id2);Graph[id1][id2] = true;Graph[id2][id1] = true;}for (int i = 0; i < k; i++) {int t;init();scanf("%d", &t);visit[t] = true;for (int i = 1; i <= n; i++) {Graph1[t][i] = 0;Graph1[i][t] = 0;}DFSTraverse();}return 0;
}
void init() { //初始化函数cnt = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {Graph1[i][j] = Graph[i][j]; //把初始的图放到Graph1中}}for (int i = 1; i <= n; i++) visit[i] = false; //重置visit数组
}
void DFS(int id) {visit[id] = true;for (int i = 1; i <= n; i++) {if (Graph1[id][i] > 0) {Graph1[id][i] = Graph1[i][id] = 0; //删除路径，防止回头if (visit[i] == false) DFS(i); //如果与它相连的结点没有被访问过，继续访问}}
}
void DFSTraverse() {for (int i = 1; i <= n; i++) {if (visit[i] == false) {DFS(i);cnt++;}}printf("%d\n", cnt - 1); //输出的是连通分量的个数-1
}