PAT甲题题解-1013. Battle Over Cities (25)-求联通分支个数
2024-08-25 15:53:34
题目就是求联通分支个数
删除一个点,剩下联通分支个数为cnt,那么需要建立cnt-1边才能把这cnt个联通分支个数求出来
怎么求联通分支个数呢
可以用并查集,但并查集的话复杂度是O(m*logn*k)
我这里用的是dfs,dfs的复杂度只要O((m+n)*k)
这里k是指因为有k个点要查询,每个都要求一下删除后的联通分支数。
题目没给定m的范围,所以如果m很大的话,dfs时间会比较小。
for一遍1~n个点,每次从一个未标记的点u开始dfs,标记该dfs中访问过的点。
u未标记过,说明之前dfs的时候没访问过该点,即表明该点与前面的点不属于同一个分支,相当于新的分支。
所以只要统计一下1~n中dfs多少次,就有多少个联通分支
删除的点最开始标记一下,就不会访问到了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
const int maxn=+;
int n,m,k;
int check[maxn]; //先标记哪些点会check,防止有重复的点做重复的工作
int ans[maxn]; //删掉节点i后剩余的连通分支数目
int vis[maxn]; //用于dfs时候的标记
struct Edge{
int to;
int next;
}edge[maxn*maxn];
int head[maxn];
int tot; void init(){
memset(head,-,sizeof(head));
tot=;
}
void add(int u,int v){
edge[tot].to=v;
edge[tot].next=head[u];
head[u]=tot++;
} void dfs(int u){
vis[u]=;
if(head[u]==-)
return;
for(int k=head[u];k!=-;k=edge[k].next){
int v=edge[k].to;
if(!vis[v]){
dfs(v);
}
}
}
/*
对于要check的点,求删除后的联通分支数,存储在ans数组里
*/
void solve(){
memset(ans,,sizeof(ans));
for(int i=;i<=n;i++){
//如果i是要被询问的
if(check[i]){
memset(vis,,sizeof(vis));
vis[i]=;
for(int j=;j<=n;j++){
//每次有没被访问过的节点,表明又是一个新的联通分支
if(!vis[j] && j!=i){
dfs(j);
ans[i]++;
}
}
}
}
}
int main()
{
int u,v;
init();
scanf("%d %d %d",&n,&m,&k);
for(int i=;i<m;i++){
scanf("%d %d",&u,&v);
add(u,v);
add(v,u);
}
memset(check,,sizeof(check));
vector<int>query;
for(int i=;i<k;i++){
scanf("%d",&u);
check[u]=;
query.push_back(u);
}
solve();
for(int i=;i<query.size();i++){
u=query[i];
printf("%d\n",ans[u]-);
}
return ;
}
最新文章
- Textview在Listview中实现跑马灯效果
- Struts2文件上传,以及各种注意事项
- ES6,ES2105核心功能一览,js新特性详解
- jQ $.extend用法
- ANDROID_MARS学习笔记_S01原始版_019_SERVICE之Transact
- eclipse手动添加源码
- .NET/Mono
- Lucene中的 Query对象
- iOS将自己的框架更新到cocopods上
- FPGA 设计总结(1)
- golang类型断言
- 桥接模式-pattern系列
- assembly.xml
- js 事件event
- 高通RFC适配RFFE-添加MIPI设备【转】
- 通过程序修改注册表键值来达到修改IE配置参数的目的
- linux 配置文件(启动文件、环境文件)启动顺序
- texturePacker黄色文件夹和蓝色文件夹
- 【BZOJ】2406 矩阵
- PrintArea打印,@media screen解决移动web开发的多分辨率问题,@media print设置打印的样式
热门文章
- 基础知识整理汇总 - Java学习(一)
- (转)python3 urllib.request.urlopen() 错误UnicodeEncodeError: &#39;ascii&#39; codec can&#39;t encode characters
- python第三十六课——2.迭代器对象
- docker tomcat jvm 使用 visualVM监控
- 使用sysbench 进行msyql oltp压力测试
- lwip lwiperf 方法进行性能测试 4.5MB/S
- bash下输入命令的几个常用快捷键
- 牛掰本机限速软件appband
- odoo之recoed.append()方法
- 【本地服务器】windows下nginx安装操作教程