HDU 4496 D-City(反向并查集)

Ch_Zaqdt

发布于 2019-01-10 14:06:50

4780

发布于 2019-01-10 14:06:50

文章被收录于专栏：Zaqdt_ACMZaqdt_ACM

题意是有n个点，m条边，刚开始这些边都是连着的，然后按顺序逐一破坏这些边，然后让你输出每破坏一次图中还剩几个集合，刚开始肯定是有一个集合的，最后都破坏完了就是n个集合了。

讲一下思路，我们可以反向思考，从正面破坏，可以从倒着连接实现，开一个ans数组标记每次连接两个点后的集合数目，比如刚开始有n个点，就让ans[i] = n，然后每次把两个集合连起来的时候就让n--，然后再用ans去存。结合代码看一下吧。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 100005;
struct Node{
  int x,y;
}Edge[MAXN];
int pre[MAXN];
int ans[MAXN];
int n,m,a,b,sum;

void init(){
  for(int i=0;i<n;i++){
    pre[i] = i;
  }
}

int Find(int x){
  if(x != pre[x]){
    pre[x] = Find(pre[x]);
  }
  return pre[x];
}

void merge(int x,int y){
  int fx = Find(x);
  int fy = Find(y);
  if(fx != fy){
    pre[fy] = fx;
    sum--;
  }
}

int main()
{
  while(~scanf("%d%d",&n,&m)){
  init();
  memset(ans,0,sizeof(ans));
  sum = n;
  for(int i=0;i<m;i++){              // 存边
    scanf("%d%d",&Edge[i].x,&Edge[i].y);
  }
  for(int i=m-1;i>=0;i--){           // 倒着并
    ans[i] = sum;
    merge(Edge[i].x,Edge[i].y);
  }
  for(int i=0;i<m;i++){
    printf("%d\n",ans[i]);
  }
}
  return 0;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018年02月23日，如有侵权请联系 cloudcommunity@tencent.com 删除

集合