BZOJ 1015 星球大战starwar 逆向并查集
2024-08-31 10:21:53
题目链接:
https://www.lydsy.com/JudgeOnline/problem.php?id=1015
题目大意:
很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天,凭着一个偶然的机遇,一支反抗军摧毁了帝国的超级武器,并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。 但好景不长,很快帝国又重新造出了他的超级武器。凭借这超级武器的力量,帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁,两个星球之间的通讯通道也开始不可靠起来。现在,反抗军首领交给你一个任务:给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序,以尽量快的速度求出每一次打击之后反抗军占据的星球的连通快的个数。(如果两个星球可以通过现存的以太通道直接或间接地连通,则这两个星球在同一个连通块中)
思路:
删点之后不好维护,所以离线下来,逆向处理,逐渐加点维护连通块个数即可。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);//不可再使用scanf printf
#define Max(a, b) ((a) > (b) ? (a) : (b))//禁用于函数,会超时
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Mem(a) memset(a, 0, sizeof(a))
#define Dis(x, y, x1, y1) ((x - x1) * (x - x1) + (y - y1) * (y - y1))
#define MID(l, r) ((l) + ((r) - (l)) / 2)
#define lson ((o)<<1)
#define rson ((o)<<1|1)
#pragma comment(linker, "/STACK:102400000,102400000")//栈外挂
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
typedef long long ll;
const int maxn = + ;
const int mod = ;//const引用更快,宏定义也更快
const int INF = 1e9;
int p[maxn];
vector<int>G[maxn];
bool vis[maxn];
stack<int>ans;
int Find(int x)
{
return x == p[x] ? x : p[x] = Find(p[x]);
}
int a[maxn];
int main()
{
int n, m, u, v;
scanf("%d%d", &n, &m);
while(m--)
{
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
for(int i = ; i < n; i++)p[i] = i;
scanf("%d", &m);
for(int i = ; i < m; i++)scanf("%d", &a[i]), vis[a[i]] = ;
for(int u = ; u < n; u++)
{
if(!vis[u])for(int i = ; i < G[u].size(); i++)
{
int v = G[u][i];
if(!vis[v])
{
int x = Find(u), y = Find(v);
p[x] = y;
}
}
}
int tot = ;
for(int i = ; i < n; i++)if(!vis[i])if(p[i] == i)tot++;
ans.push(tot);
for(int i = m - ; i >= ; i--)
{
int u = a[i], cnt = ;
vis[u] = ;
for(int j = ; j < G[u].size(); j++)
{
int v = G[u][j];
if(!vis[v])
{
int x = Find(u), y = Find(v);
if(x != y)
{
cnt++;
p[x] = y;
}
}
}
tot = tot - cnt + ;
ans.push(tot);
}
while(!ans.empty())
{
printf("%d\n", ans.top()), ans.pop();
}
return ;
}
最新文章
- Ruby On Rails 常用的精品Gem汇总
- 1分钟学会Markdown语法
- Python 通过print将数据保存到文件中
- No module named BeautifulSoup
- my_vimrc
- java连接oracle数据库的实现代码
- PHP实现登录,注册,密码修改
- Binders 与 Window Tokens(窗体令牌)
- SQLite 分离数据库(http://www.w3cschool.cc/sqlite/sqlite-detach-database.html)
- poj2186(tarjan缩点)
- python 的基础 学习 第六天 基础数据类型的操作方法 字典
- Adobe Flex初记
- 一篇很好的java异常框架讲解
- SEO-搜索引擎优化
- [C]语法, 知识点总结(一. 进制, 格式化输入/出, 指针)
- VS2017写的exe调用Delphi 7写的DLL
- echarts一些笔记
- ASP.NET:邮件服务器与客户端
- 运维监控之zabbix(yum安装)
- Java类型强制转换