并查集： 1.查询元素a和b是否为一组 2.将元素a和b的组合并到一起 特点：只注重树的结构，不注重树的节点的位置。 优化方式： 1.使用rank数组记录每棵树的深度，小的向大的合并。 2.在查询过程中，所有的经过的点都换为同一个根。
int par[N],RANK[N]; void init(int n){//每个节点的根初始为自己 for(int i=1;i<=n;i++){ par[i]=i; rank[i]=0; } } int find(int x){//查询树的根 if(par[x]==x)return x; return par[x]=find(par[x]);//根据上一个节点递归找根 } void unite(int x,int y){//合并操作 x=find(x); y=find(y); if(x==y)return; if(rank[x]<rank[y]){//rank小的边向大的边连线 par[x]=y; } else{ par[y]=x; if(rank[x]==rank[y])rank[x]++; } } bool same(int x,int y){//判断是否相同 return find(x)==find(y); }POJ 1182 使用并查集判断是否是一个组，或者是否隔了一个组
#include<iostream> #include<cstdio> #define N 50005 using namespace std; int par[N*3],rank[N*3]; void init(int n){//每个节点的根初始为自己 for(int i=1;i<=n;i++){ par[i]=i; rank[i]=0; } } int find(int x){//查询树的根 if(par[x]==x)return x; return par[x]=find(par[x]);//根据上一个节点递归找根 } void unite(int x,int y){ x=find(x); y=find(y); if(x==y)return; if(rank[x]<rank[y]){//rank小的边向大的边连线 par[x]=y; } else{ par[y]=x; if(rank[x]==rank[y])rank[x]++; } } bool same(int x,int y){ return find(x)==find(y); } int main(){ int n,k; cin >> n >> k; int d,x,y; int ans=0; init(3*n); for(int i=1;i<=k;i++){ scanf("%d%d%d",&d,&x,&y); if(x<=0||y<=0||x>n||y>n){ ans++; continue; } if(d==1){ if(same(x,y+n)||same(x,y+2*n)){ ans++;//不在同一类 } else{ unite(x,y); unite(x+n,y+n); unite(x+2*n,y+2*n); } } else{ if(same(x,y)||same(x,y+2*n))ans++;//同一组或者跨越了一个组 else{ unite(x,y+n); unite(x+n,y+2*n); unite(x+2*n,y); } } } cout << ans << endl; return 0; }