C130 并查集 P1197 [JSOI2008] 星球大战

视频链接：

P1197 [JSOI2008] 星球大战 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

// 并查集
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int N=400005;
int h[N],from[N],to[N],ne[N],idx;
void add(int u,int v){
  from[++idx]=u; to[idx]=v;
  ne[idx]=h[u]; h[u]=idx;
}
int n,m,k,x,y,tot;
int a[N],be[N];
int p[N],ans[N];

int find(int x){
  return p[x]==x?x:p[x]=find(p[x]);
}
int main(){
  scanf("%d%d",&n,&m);
  for(int i=0;i<n;++i) p[i]=i;
  for(int i=1;i<=m;++i)
    scanf("%d%d",&x,&y),add(x,y),add(y,x);
  scanf("%d",&k);
  for(int i=1;i<=k;i++){
    scanf("%d",&x);
    a[i]=x;  //记录被摧毁的星球
    be[x]=1; //标记x被摧毁
  }
  tot=n-k; //剩余星球独立成块
  for(int i=1;i<=2*m;i++){ //枚举所有边
    //两球都没被摧毁且没在同一集合，则合并
    if(!be[from[i]]&&!be[to[i]]
      &&find(from[i])!=find(to[i])){
      p[find(from[i])]=find(to[i]);
      tot--; //合并后，连通块数-1
    }
  }
  ans[k+1]=tot; //摧毁k个星球后的答案
  for(int j=k;j>=1;j--){ //把摧毁的星球逆向修复
    x=a[j]; be[x]=0;
    tot++; //因为修复一个点，连通块数+1
    for(int i=h[x];i;i=ne[i]){ //枚举x的临接点
      //两球都没被摧毁且没在同一集合，则合并
      if(!be[to[i]]&&find(x)!=find(to[i])){
        p[find(x)]=find(to[i]);
        tot--; //合并后，连通块数-1
      }
    }
    ans[j]=tot; //修复完这个点后，连通块的个数
  }
  for(int i=1;i<=k+1;++i)printf("%d\n",ans[i]);
}

信息学奥赛一本通（C++版）1347【例4-8】格子游戏  在线评测系统 (ssoier.cn)

// 并查集判断是否存在环：
// 1.将每个坐标看成一个点值，将所有的坐标横纵坐标都减1，
//   第一个位置即(1,1)看成是0，(1,2)看成是1，依次类推，
//   假设当前点是(x,y),则该点的映射值是a=(x*n+y)，
//   若向下画，则b=(x+1)*n+y,若向右画，则b=x*n+y+1
// 2.枚举所有操作，判断a和b是否在同一个集合，
//   若在同一个集合则标记此操作可以让格子形成环
//   若不在同一个集合，则需要将两个集合进行合并
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=40005;
int n,m;
int p[N];

int get(int x,int y){ 
  return x*n+y;
}
int find(int x){
  return p[x]==x?x:p[x]=find(p[x]);
}
int main(){
  cin>>n>>m;
  for(int i=0;i<n*n;i++) p[i]=i;
  int res=0;
  for(int i=1;i<=m;i++){
    int x,y,a,b; char d;
    cin>>x>>y>>d;
    x--,y--;
    a=get(x,y); //a点
    if(d=='D') b=get(x+1,y); //b点
    else b=get(x,y+1);
    a=find(a),b=find(b);
    if(a==b){ //形成环
      cout<<i; return 0;
    }
    p[a]=b;
  }
  cout<<"draw";
}