并查集 1、什么叫并查集 并查集（union-find set）是一种用于分离集合操作的抽象数据类型。它所处理的是“集合”之间的关系，即动态地维护和处理集合元素之间复杂的关系，当给出两个元素的一个无序对(a,b)时，需要快速“合并”a和b分别所在的集合，这其间需要反复“查找”某元素所在的集合。“并”、“查”和“集”三字由此而来。在这种数据类型中，n个不同的元素被分为若干组。每组是一个集合，这种集合叫做分离集合（disjoint set）。并查集支持查找一个元素所属的集合以及两个元素各自所属的集合的合并。
#include<iostream> #include<cstdio> using namespace std; #define maxn 20001 int father[maxn]; int m,n,i,x,y,q; /* int find(int x) //用非递归的实现 { while (father[x] != x) x= father[x]; return x; } */ int find(int x) //用递归的实现 { if (father[x] != x) father[x] = find(father[x]); //路径压缩 return father[x]; } void unionn(int r1,int r2) { father[r2] = r1; } int main() { freopen("relation.in","r",stdin); freopen("relation.out","w",stdout); cin >> n >> m; for (i = 1; i <= n; i++) father[i] = i; //建立新的集合，其仅有的成员是i for (i = 1; i <= m; i++) { scanf("%d%d",&x,&y); int r1 = find(x); int r2 = find(y); if (r1 != r2) unionn(r1,r2); } cin >> q; for (i = 1; i <= q; i++) { scanf("%d%d",&x,&y);; if (find(x) == find(y)) printf("Yes\n"); else printf("No\n"); } return 0; }最小生成树 Prim算法 Prim算法采用与Dijkstra、Bellman-Ford算法一样的“蓝白点”思想：白点代表已经进入最小生成树的点，蓝点代表未进入最小生成树的点。 算法描述： 以1为起点生成最小生成树，min[v]表示蓝点v与白点相连的最小边权。 MST表示最小生成树的权值之和。 a）初始化：min[v]= ∞(v≠1); min[1]=0;MST=0; b）for (i = 1; i<= n; i++) 1.寻找min[u]最小的蓝点u。 2.将u标记为白点 3.MST+=min[u] 4.for 与白点u相连的所有蓝点v if (w[u][v]<min[v]) min[v]=w[u][v]; c）算法结束： MST即为最小生成树的权值之和
