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.

也就是说, 有很多个城市构成一张图, 去掉某一个城市,以及和这个城市连接的所有边, 问使得剩下的所有城市之间连通需要再加几条边

算法分析:

算法其实就是DFS, 在图上去掉一个node, 求剩下的图的连通component, 有多少个连通的component(设有T个connected component), 这个数目减一(T-1)就是需要加的边数. 至于为什么, 其实问一个更简单的问题就能理解了, 比如我们想使得T个孤立的点都连通, 也就是任意两点之间都有路径, 那么用T-1条边把他们连成一颗树是不是就行了? 同样道理, 题目中去掉一个节点(city)之后的每一个连通子图就是我们的孤立的点, 所以需要T-1条边. 找连通component利用dfs就可以了. DFS完所有剩下的node直到每个node都有一个自己的component id即可. 下面的代码可以通过PAT OJ

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

int adjList[NNodes][NNodes];
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);
        adjList[index1][index2] = adjList[index2][index1]= 1;
    }
    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