# PAT 解题报告 1013. Battle Over Cities (25)

## Overview

PAT 1013 Battle Over Cities可以这么解决: 利用DFS求剩下的图的连通component数量, 有多少个连通的component (设有T个connected component), 这个数目减一, that is (T-1) 就是需要加的边数.

## PAT 1013: Battle Over Cities Problem

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.

## 算法分析：

```#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <iomanip>
#define NNodes 1010
using namespace std;

int disJointSet[NNodes];
int classes;

void dfsUnion(int root, int city, int N) {
disJointSet[root] = classes;
for(int i=1; i<=N; i++)
{
if(adjList[root][i] && i != city && !disJointSet[i]) {
dfsUnion(i, city, N);
}
}
}

int main(void) {
int N, M, K;
scanf("%d %d %d",&N, &M, &K);
for(int i=0; i<M; i++) {
int index1, index2;
scanf("%d %d", &index1, &index2);
}
for(int i=0; i<K; i++) {
memset(disJointSet, 0, sizeof(int)*NNodes);
classes = 0;
int city;
scanf("%d", &city);
if(1 == N || 2 == N) {
printf("0\n");
continue;
}
for(int i=1; i<=N; i++) {
if(!disJointSet[i] && i != city) {
classes++;
dfsUnion(i, city, N);
}
}
printf("%d\n", classes-1);
}
return 0;

}
```

## Summary

PAT 1013 Battle Over Cities可以这么解决: 利用DFS求剩下的图的连通component数量, 有多少个连通的component (设有T个connected component), 这个数目减一, that is (T-1) 就是需要加的边数.

Written on April 18, 2013