考研数据结构之并查集
小知识，大挑战！本文正在参与“程序员必备小知识”创作活动
漏网之鱼：逻辑结构——“集合”
逻辑结构——数据元素之间的逻辑关系是什么？
集合的两个基本操作——“并”和“查”
Find ——“查”操作：确定一个指定元 素所属集合 Union ——“并”操作：将两个不想交 的集合合并为一个 注：并查集（Disjoint Set）是逻辑结 构——集合的一种具体实现，只进行 “并”和“查”两种基本操作
如何“查”到一个元素到底属于哪一个集合？ —— 从指定元素出发，一路向北，找到根节点 如何判断两个元素是否属于同一个集合？ —— 分别查到两个元素的根，判断根节点是否相同即可
#include<iostream> using namespace std; #define SIZE 13 int UFSets[SIZE]; //集合元素组 //初始化并查集 void Initial(int S[]){ for(int i=0;i<SIZE;i++) S[i]=-1; } //Find "查"操作，找X所属集合（返回X所属根结点） int Find(int S[],int X){ while(S[X]>=0) //循环寻找X的根 X=S[X]; return X; } //Union "并"操作，讲两个集合合并为一个 void Union(int S[],int Root1,int Root2){ //要求Root1与Root2是不同集合 if(Root1==Root2) return; //将根Root2连接到另一根Root1下面 S[Root2]=Root1; } //Union "并"操作，小树合并到大树 void Union1(int S[],int Root1,int Root2){ if(Root1==Root2) return; if(S[Root2]>S[Root1]){ S[Root1]+=S[Root2]; S[Root2]=Root1; //小树合并到大树 }else{ S[Root2]+=S[Root1]; S[Root1]=Root2; } } //用并查集判断一个图有几个连通分量（图用邻接矩阵表示） int ComponentCount(int g[5][5]){ //g[5][5]是一个二维数组表示的邻接矩阵 int S[5]; for(int i=0;i<5;i++) S[i]=-1; //定义，初始化并查集 for(int i=0;i<5;i++) for(int j=i+1;j<5;j++) if(g[i][j]>0){ int iRoot=Find(S,i); int jRoot=Find(S,j); if(iRoot!=jRoot) Union1(S,iRoot,jRoot); } int count=0; for(int i=0;i<5;i++) if(S[i]<0) count++; return count; } //用并查集判断一个图是否有环（图用邻接矩阵表示） int hasAcyclic(int g[5][5]){ //g[5][5]是一个二维数组表示的邻接矩阵 int S[5]; //初始化并查集 for(int i=0;i<5;i++) S[i]=-1; for(int i=0;i<5;i++) for(int j=i+1;j<5;j++) if(g[i][j]>0){ int iRoot=Find(S,i); int jRoot=Find(S,j); if(iRoot!=jRoot) Union(S,iRoot,jRoot); else return 1;//在一个连通子图中，但凡再多一条边，必有环 } return 0;//图中没环 } int main(){ return 0; }
作者：有出路
链接：https://juejin.cn/post/7024686291283361823