hdu 4496 其实还是并查集
2024-09-01 13:45:11
Problem Description
Luxer is a really bad guy. He destroys everything he met.
One day Luxer went to D-city. D-city has N D-points and M D-lines. Each D-line connects exactly two D-points. Luxer will destroy all the D-lines. The mayor of D-city wants to know how many connected blocks of D-city left after Luxer destroying the first K D-lines in the input.
Two points are in the same connected blocks if and only if they connect to each other directly or indirectly.
One day Luxer went to D-city. D-city has N D-points and M D-lines. Each D-line connects exactly two D-points. Luxer will destroy all the D-lines. The mayor of D-city wants to know how many connected blocks of D-city left after Luxer destroying the first K D-lines in the input.
Two points are in the same connected blocks if and only if they connect to each other directly or indirectly.
Input
First line of the input contains two integers N and M.
Then following M lines each containing 2 space-separated integers u and v, which denotes an D-line.
Constraints:
0 < N <= 10000
0 < M <= 100000
0 <= u, v < N.
Then following M lines each containing 2 space-separated integers u and v, which denotes an D-line.
Constraints:
0 < N <= 10000
0 < M <= 100000
0 <= u, v < N.
Output
Output M lines, the ith line is the answer after deleting the first i edges in the input.
逆向思维的重要性!
#include<cstdio>
#include<iostream>
#include<string.h>
#include<stack>
#define maxn 10005
using namespace std;
int pre[maxn];
int num;
void init()
{
for(int i=;i<maxn;i++) pre[i]=i;
}
int find(int x)
{
if(pre[x]==x) return x;
else return pre[x]=find(pre[x]);
}
void merge(int x,int y)
{
x=find(x);
y=find(y);
if(x!=y)
{
num--;
pre[y]=x;
}
}
int main()
{
cin.sync_with_stdio(false);
int n,m;
while(cin>>n>>m)
{
stack<int> fuck,fuck2;
int ret[m];
while(m--)
{
int x,y;
cin>>x>>y;
fuck.push(x),fuck.push(y);
}
init();
num=n;
int rett=;
while(!fuck.empty())
{
int yy=fuck.top();
fuck.pop();
int xx=fuck.top();
fuck.pop();
ret[rett++]=num;
merge(xx,yy);
}
for(int i=rett-;i>=;i--) cout<<ret[i]<<endl;
}
return;
}
最新文章
- Snort 安装 配置 - Archlinux
- block,inline,inline-block的区别
- Codeforces Round #281 (Div. 2) D. Vasya and Chess 水
- cocos2d-x 详解之 CCLayer(触摸事件)
- map的例子
- oracle进制转换
- Java设计模式---组合模式
- Material风格的Quick组件,妈妈再也不用担心我的界面不好看了
- linux win7双系统
- 浅谈mapreduce程序部署
- NOIP2001-普及组复赛-第二题-最大公约数和最小公倍数问题
- USACO Section 1.2 Transformations 解题报告
- [ext4]06 磁盘布局 - 特殊inode
- ELK学习总结(3-1)elk的基本查询
- tensorflow从入门到放弃-0
- Jmeter post请求传参问题
- 树中的路径和 Sum of Distances in Tree
- Android Studio 常见问题及解决方法
- 搭建Hexo博客(三)—换电脑继续写Hexo博客
- Linux 查看进程的线程数