当前位置：首页 > 编程日记 > 正文

1013 Battle Over Cities(图的DFS解法)

编程日记 2024-09-06 14:30:00

这题的背景是战争年代，假如城市1被占领，那么所有和城市1相关的公路都要被炸毁，但是这样一来，2和3就不连通了，所以需要补修一条23之间的公路。但是换做城市2或3被占领，1和另一座城市是联通的，并不需要补修公路。

因此这题是求删去一个结点后，剩下的图中的连通子图的数量，再减去1就是最终要求的结果了。

两个犯傻的地方：

1. 我用DFS和邻接表做这题，还开了两个邻接表，一个用于保存和恢复，增加了不少代码量，其实无需真正去“炸毁公路(删除边)”，只要遍历到被占领的城市跳过即可。

2. 由于DFS需要维护一个哈希数组，并在每次遍历前恢复零，但是注意这里城市的编号从1开始，所以调用fill函数的话，一定是下面这样

fill(vis,vis+allCityNum+1,0);//加一必不可少

第二个参数是数组名+城市的数目+1！！

关于DFS的写法：

之前想着删边的时候，有两类边要删除，假设被占领城市的编号是lostIdx，那么G[lostIdx]所在的向量要整个clear()，其他的i≠lostIdx的G[i]里面如果存在lostIdx也要删除。这两个分别对应dfsTrave()和dfs(int idx)里面的判断

void dfsTrave(){for(int j=1;j<=allCityNum;j++){if(j!=lostIdx&&vis[j]==0){dfs(j);needNum ++;}}
}void dfs(int idx){if(idx==lostIdx)return;else{vis[idx] = 1;for(int i=0;i<G[idx].size();i++){int u = G[idx][i];if(vis[u]==0)dfs(u);}}}

此外：

我是把需要炸毁的城市数目记作-1，进行一次dfs就加一，所以需要判断一开始是不是只有一座城市，不然会输出-1来。

AC代码

#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
typedef long long LL;using namespace std;const int maxn = 1010;//总城市数上限 vector<int> G[maxn];int allCityNum,lostIdx;int needNum = -1;
bool vis[maxn] = {0};void dfs(int idx){if(idx==lostIdx)return;else{vis[idx] = 1;for(int i=0;i<G[idx].size();i++){int u = G[idx][i];if(vis[u]==0)dfs(u);}}}void dfsTrave(){for(int j=1;j<=allCityNum;j++){if(j!=lostIdx&&vis[j]==0){dfs(j);needNum ++;}}
}int main(){int wayNum,lostCityNum;scanf("%d %d %d",&allCityNum,&wayNum,&lostCityNum);for(int i=0;i<wayNum;i++){int ct1,ct2;scanf("%d %d",&ct1,&ct2);G[ct1].push_back(ct2);G[ct2].push_back(ct1);}for(int i=0;i<lostCityNum;i++){scanf("%d",&lostIdx);if(allCityNum == 1){printf("0\n");}else{ //关键操作needNum = -1; fill(vis,vis+allCityNum+1,0);//加一必不可少 dfsTrave();printf("%d\n",needNum);}}return 0;
}

https://www.dkcj.cn/info/17548.html

1013 Battle Over Cities(图的DFS解法)

相关文章：

你必须了解的微服务架构设计的10个要点！

企业信息化中常见决策点应对

WebView调试

1013 Battle Over Cities(并查集解法)

FastDFS为什么要结合Nginx？

STL容器[34]

企业可视化报表工具选型经验分享

1003 Emergency(Dijkstra，Bellman-Ford，SPFA三种解法)

存储过程4-前台

安卓学习-其他-文件读写

X5同层播放器应用实践

1007 Maximum Subsequence Sum(两种思路)

C#学习-EF在三层中使用

各大IT公司笔试真题汇总开发人员一定要加入收藏夹的网站(收藏)

Python编写Hive UDF

1045 Favorite Color Stripe(LIS解法)

5.8fork父子进程

word表格自动编号

Vue API(directives) 自定义指令

1045 Favorite Color Stripe(LCS解法) 需再理解

C++ primer第五版随笔--2015年1月6日

Python性能分析指南——中

1040 Longest Symmetric String 需再做

回顾2009，展望2010。

Linux Mint 19 安装Gnome Boxes 新建失败

1057 Stack

【译】使用自定义ViewHelper来简化Asp.net MVC view的开发------part1

看书挑剔,只看经典

0-1背包使用一维dp数组时为何v要从大到小枚举

异步编程模型--使用 IAsyncResult 对象