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

简介: PAT (Advanced Level) Practice - 1013 Battle Over Cities(25 分)

题目链接:点击打开链接


题目大意:给出一张无向图,以及几条边。要求当去掉其中的一个顶点后为了使剩下的顶点可以连通需要增加多少条边。


解题思路:其实只要考虑去掉这个顶点后,剩余的顶点可以组成几个独立的区域,假设该区域数为t,则需要增加的边即为t-1。(即:求剩余的连通分量个数-1)。


AC 代码


/

#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1010;
int n,m,k;
int vis[maxn];
int g[maxn][maxn];
void dfs(int s)
{
    vis[s]=1;
    for(int i=1;i<=n;i++)
        if(!vis[i] && g[s][i]==1) dfs(i);
}
int main()
{
    int u,v;
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&u,&v);
            g[u][v]=g[v][u]=1;
        }
        while(k--)
        {
            scanf("%d",&u);
            mem(vis,0);
            vis[u]=1;
            int rs=0;
            for(int i=1;i<=n;i++)
            {
                if(!vis[i])
                {
                    dfs(i);
                    rs++;
                }
            }
            printf("%d\n",rs-1);
        }
    }
    return 0;
}
目录
打赏
0
0
0
0
38
分享
相关文章
如何使用Traceroute定位网络问题?
`Traceroute` 是网络诊断工具,用于追踪数据包从源主机到目标主机的路径,帮助定位网络延迟、路由故障或中间节点问题。常用参数包括禁用DNS解析(`-n`)、指定最大跳数(`-m`)、每跳探测包数量(`-q`)等。结果解读涉及时间值、符号含义(如`*`表示未响应),并可进行高级用法如指定源接口、强制使用ICMP或TCP协议。常见问题包括中间节点高延迟、路径终点无法到达和路径环路,需根据具体情况进行排查和解决。
755 1
掌握Docker容器化:提升开发效率与应用部署
【10月更文挑战第4天】在现代软件开发中,Docker容器化技术因其轻量级、可移植和快速部署的特点,成为提升开发效率和简化部署流程的关键工具。本文介绍了Docker的基本概念、核心组件及其优势,并探讨了如何在开发环境中搭建、微服务架构及CI/CD流程中有效利用Docker,助力软件开发更加高效便捷。
通过函数计算节点实现GitHub实时数据分析与结果发送
开发人员在基于GitHub开源项目进行开发时会产生海量事件,GitHub会记录每次事件的类型、详情、开发者和代码仓库等信息,并开放其中的公开事件。DataWorks提供“Github十大热门编程语言”模板,通过对GitHub中公开数据集进行加工和分析,并将分析结果以邮箱的方式发送给指定用户。运行本案例后,您将得到Github中Top10编程语言每小时被提交的次数与排行。
166 10
Git学习笔记(一):基础与应用
本文档详细介绍了如何将本地项目关联到Gitee上的空仓库并上传代码,以及如何验证本机与Git服务器的SSH连接。同时,还概述了Git的基本概念、安装步骤、初始配置、常见命令及如何配置多个SSH-Key,适用于初学者快速上手Git操作。
221 51
Git学习笔记(一):基础与应用
|
10月前
|
载波聚合:赋能5G高速率通信的关键技术
载波聚合:赋能5G高速率通信的关键技术
1701 5
避免低级错误:深入解析Java的ConcurrentModificationException异常
在软件开发中,我们常常会遇到各种错误和异常。其中有一类比较低级但又常见的错误就是`ConcurrentModificationException`异常。最近了我就写了个这种异常,这个异常通常发生在使用迭代器遍历集合时,同时对集合进行修改,从而导致迭代器检测到集合结构发生变化而抛出异常。在测试环境中可能因为数据量较小或者测试场景不充分未能显现问题,但一旦部署到生产环境,场景增多,并发操作增多,这个低级错误就会爆发。
413 0
避免低级错误:深入解析Java的ConcurrentModificationException异常
volatile关键字的作用
volatile关键字的作用
79 0
React&Nest.js全栈社区平台(三)——🐘对象存储是什么?为什么要用它?
React&Nest.js全栈社区平台(三)——🐘对象存储是什么?为什么要用它?
人工智能,应该如何测试?(二)数据挖掘篇
在AI模型开发中,数据起着决定性作用,模型的性能往往受限于数据的质量和量级。建模工程师大部分时间都在与数据打交道,而中国在AI发展上与国外的主要差距并不在于计算能力,而是高质量的数据。测试人员不仅需要评估模型效果,也需要处理数据,包括数据采集、质量监控、构造、ETL(提取、转换、加载)和特征工程等。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等