L2-013 红色警报DFS+染色
题目链接
https://pintia.cn/problem-sets/994805046380707840/problems/994805063963230208
思路
对于每一个城市我们都有一个over
标记 over[i]=true
表示的是第 i i i 个城市已经被攻占下了,对于每一个城市被攻占后我们就将其标为true
并且将其所有联通的城市全都标记为true
(其实就是一个图的遍历),然后每次我们拿攻占前和攻占后的连通块的数量进行对比,如果发现连通块的数量增大了(除去被攻占的这个城市),那么说明国家被分割了,于是我们输出Red Alert: City k is lost!
否则我们只需要输出 ity k is lost.
,最后如果攻占的城市的数量为 n n n 的话,最后输出 Game Over.
代码
#include<bits/stdc .h>
using namespace std;
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair<int,int>
#define INF 0x3f3f3f3f
const int N = 5e2 10;
bool mp[N][N];
bool vis[N],over[N];
int n,m;
void dfs(int u){
if(vis[u]) return;
vis[u] = true;
for(int i = 0;i < n; i) {
if(i != u && mp[u][i] && !over[i])
dfs(i);
}
}
int get_num(){
int ans = 0;
memset(vis,false,sizeof vis);
for(int i = 0;i < n; i) {
if(!vis[i] && !over[i]){
dfs(i);
ans ;
}
}
return ans;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
int u,v;
for(int i = 1;i <= m; i) {
cin>>u>>v;
mp[u][v] = mp[v][u] = true;
}
int k,t,num = get_num();
cin>>k;
for(int i = 1;i <= k; i) {
cin>>t;
over[t] = true;
int loc = get_num();
if(loc > num) {
cout<<"Red Alert: City "<<t<<" is lost!"<<endl;
} else {
cout<<"City "<<t<<" is lost."<<endl;
}
num = loc;
}
if(k == n) cout<<"Game Over."<<endl;
return 0;
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfeebi
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01