题目就是求联通分支个数
删除一个点,剩下联通分支个数为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 ;
}

最新文章

  1. Textview在Listview中实现跑马灯效果
  2. Struts2文件上传,以及各种注意事项
  3. ES6,ES2105核心功能一览,js新特性详解
  4. jQ $.extend用法
  5. ANDROID_MARS学习笔记_S01原始版_019_SERVICE之Transact
  6. eclipse手动添加源码
  7. .NET/Mono
  8. Lucene中的 Query对象
  9. iOS将自己的框架更新到cocopods上
  10. FPGA 设计总结(1)
  11. golang类型断言
  12. 桥接模式-pattern系列
  13. assembly.xml
  14. js 事件event
  15. 高通RFC适配RFFE-添加MIPI设备【转】
  16. 通过程序修改注册表键值来达到修改IE配置参数的目的
  17. linux 配置文件(启动文件、环境文件)启动顺序
  18. texturePacker黄色文件夹和蓝色文件夹
  19. 【BZOJ】2406 矩阵
  20. PrintArea打印,@media screen解决移动web开发的多分辨率问题,@media print设置打印的样式

热门文章

  1. 基础知识整理汇总 - Java学习(一)
  2. (转)python3 urllib.request.urlopen() 错误UnicodeEncodeError: &#39;ascii&#39; codec can&#39;t encode characters
  3. python第三十六课——2.迭代器对象
  4. docker tomcat jvm 使用 visualVM监控
  5. 使用sysbench 进行msyql oltp压力测试
  6. lwip lwiperf 方法进行性能测试 4.5MB/S
  7. bash下输入命令的几个常用快捷键
  8. 牛掰本机限速软件appband
  9. odoo之recoed.append()方法
  10. 【本地服务器】windows下nginx安装操作教程