PAT (Advanced Level) Practice 1013 Battle Over Cities (25分)

我不是女神ヾ 2023-06-30 02:37 19阅读 0赞

题意：一个连通图，删除一个结点后，至少连几条线可以将图再次还原成联连通图。显然，两个连通分量要一条，三个连通分量要两条，....N个连通分量要N-1条。深度优先搜索最外层的循环可判断到底有几个连通分量。

#include <iostream>
    #include<stdio.h>
    #define maxn 1001
    using namespace std;
    int G[maxn][maxn]={0};
    int temp[maxn][maxn]={0};
    bool visited[maxn]={false};
    int N,M,K;
    void dfs(int index){
        visited[index] = true;
        for(int i=1;i<=N;i++){
            if(visited[i]==false&&temp[index][i]==1){
                dfs(i);
            }
        }
    }
    int check(int city){
        for(int i=1;i<=N;i++){
                visited[i] = false;
            for(int j=1;j<=N;j++){
                temp[i][j] = G[i][j];
            }
        }
        for(int i=1;i<=N;i++){
            temp[i][city] =temp[city][i] = 0;
        }
        int turn = 0;
        visited[city] = true;
        for(int i=1;i<=N;i++){
            if(visited[i]==false){
                turn++;
                dfs(i);
            }
        }
        return turn;
    }
    int main()
    {
        scanf("%d%d%d",&N,&M,&K);
        for(int i=0;i<M;i++){
            int v1,v2;
            scanf("%d%d",&v1,&v2);
            G[v1][v2] = G[v2][v1] = 1;
        }
        for(int i=0;i<K;i++){
            int check_city;
            scanf("%d",&check_city);
            printf("%d\n",check(check_city)-1);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，19人围观）

还没有评论，来说两句吧...

相关阅读

相关 PAT (Advanced Level) Practice 1013 Battle Over Cities (25分)

题意：一个连通图，删除一个结点后，至少连几条线可以将图再次还原成联连通图。显然，两个连通分量要一条，三个连通分量要两条，....N个连通分量要N-1条。深度优先搜索最外层的循环

我不是女神ヾ/ 2023年06月30日 02:37/ 0 赞/ 20 阅读

相关【PAT (Advanced Level) Practice】1086 Tree Traversals Again (25 分)

众所周知只有前序遍历和后序遍历是不可能推出中序遍历的，所以我就不废话了由树的前序遍历和中序遍历可以推后序遍历由树的中序遍历和后序遍历可以推前序遍历 incl

短命女/ 2023年01月24日 02:08/ 0 赞/ 35 阅读

相关【PAT (Advanced Level) Practice】1051 Pop Sequence (25 分)

1051 Pop Sequence (25 分) Given a stack which can keep M numbers at most. Push N number

梦里梦外;/ 2023年01月23日 10:47/ 0 赞/ 24 阅读

相关【PAT (Advanced Level) Practice】1037 Magic Coupon (25 分)

题意：给出两个集合，从这两个集合里面选出数量相同的元素进行一对一相乘，求能够得到的最大乘积之和。题解：对每个集合，将正数和负数分开考虑，将每个集合里的整数从大到小排

布满荆棘的人生/ 2023年01月23日 05:59/ 0 赞/ 31 阅读

相关【PAT (Advanced Level) Practice】1093 Count PAT‘s (25 分)

1093 Count PAT’s (25 分) The string APPAPT contains two PAT’s as substrings. The first

我会带着你远行/ 2022年10月19日 12:58/ 0 赞/ 153 阅读

相关【PAT (Advanced Level) Practice】PAT (Advanced Level) Practice

1006 Sign In and Sign Out (25 分) At the beginning of every day, the first person who s

川长思鸟来/ 2022年10月12日 01:40/ 0 赞/ 25 阅读

相关 Python实现Pat 1013. Battle Over Cities (25)

[题目][Link 1] It is vitally important to have all the cities connected by highways in

浅浅的花香味﹌/ 2022年06月03日 20:15/ 0 赞/ 137 阅读

相关 1013. Battle Over Cities (25)

It is vitally important to have all the cities connected by highways in a war. If a city

小灰灰/ 2022年05月31日 08:16/ 0 赞/ 130 阅读

相关 1013 Battle Over Cities (DFS+连同分量)

1013 Battle Over Cities （25 point(s)） It is vitally important to have all the cities co

蔚落/ 2022年03月22日 13:40/ 0 赞/ 141 阅读

相关 PAT甲级 - 1013 Battle Over Cities （25 分）

题目链接：[PAT甲级 - 1013 Battle Over Cities （25 分）][PAT_ - 1013 Battle Over Cities _25] It is

雨点打透心脏的1/2处/ 2022年03月17日 01:10/ 0 赞/ 186 阅读