PAT(甲级) 1013 Battle Over Cities (25point(s))

题目

题目链接

思路

这道题大意是给你一个连通图,删去某一点后,求有几个连通分量;
用邻接矩阵法存储图,因为删去城市有K种可能,所以要循环K次;
每次循环时都要依次dfs检查每个城市,看这个城市与哪个城市相连,共循环N ^ 2次

知识点

二维vector的初始化方法;
在Java中用户不能调用构造方法,总是用new通过系统调用,所以不会出现类型()直接初始化的方法;
但c++允许直接调用构造方法,所以有vector(size,value)的方法出现;

代码

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> v(1010, vector<int>(1010,0));//图的邻接矩阵
bool check[1010];
int N = 0;//总的城市数量

//深度优先递归访问每个城市
void dfs(int node){
    check[node] = true;
    for(int i=1; i<=N; i++){
    //如果这个城市没有访问过,并且与一个城市相连,则访问另一个城市
        if(check[i]==false && v[node][i]==1){
            dfs(i);
        }
    }
}

int main(){
    int M, K;
    scanf("%d%d%d", &N, &M, &K);
    for(int i=0; i<M; ++i){
        int a, b;
        scanf("%d%d",&a, &b);
        v[a][b] = v[b][a] = 1;
    }
    
    for(int i=0; i<K; ++i){
        fill(check, check+1010, false);
        int a = 0, cnt = 0;
        scanf("%d", &a);
        check[a] = true;
        for(int j=1; j<=N; ++j){
            //如果没有访问过,就递归访问
            if(check[j] == false){
                dfs(j);
                ++cnt;
            }
        }
        printf("%d\n",cnt-1);
    }
    
    return 0;
}
PAT(甲级)  1013 Battle Over Cities (25point(s))PAT(甲级)  1013 Battle Over Cities (25point(s)) yhjf456 发布了29 篇原创文章 · 获赞 6 · 访问量 288 私信 关注
上一篇:Spring MVC简介


下一篇:1028 List Sorting (25point(s))