社区讨论
【玄关】思路感觉大体没问题 但是样例过不了
P1197[JSOI2008] 星球大战参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @m331cg38
- 此快照首次捕获于
- 2024/11/04 21:06 去年
- 此快照最后确认于
- 2025/11/04 15:20 4 个月前
思路大概就是假设所有应该被摧毁的城市全部被摧毁,统计存活的城市的联通块,然后从后往前每次依次连接所有关于本次被摧毁城市的边。
Code:
CPP#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+5;
int n,m,k,ans;
vector<int>g[N];
map<int,bool>vis;
int pre[N],broke[N],res[N];
int root(int x){
return pre[x]=(pre[x]==x?x:root(pre[x]));
}
void merge(int u,int v){
int ru=root(u),rv=root(v);
if (ru!=rv){
ans++;
pre[ru]=rv;
}
}
bool isCon(int u,int v){
return root(u)==root(v);
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
for (int i=0;i<n;i++)pre[i]=i;
for (int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
cin>>k;
for (int i=1;i<=k;i++){
cin>>broke[i];
vis[broke[i]]=1;
}
for (int i=0;i<n;i++){
if (g[i].size()&&!vis[i]){
for (const auto &j:g[i]){
if (!vis[j]){
merge(i,j);
}
}
}
}
res[k+1]=n-k-ans;
ans=0;
for (int i=k;i>=1;i--){
for (const auto &j:g[broke[i]]){
if (!j){
merge(broke[i],j);
}
}
cout<<ans<<"\n";
res[i]=res[k+1]-ans+1;
vis[broke[i]]=0;
ans=0;
}
for (int i=1;i<=k+1;i++)cout<<res[i]<<"\n";
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...