集合运算

集合运算的方法可以运用到很多场景，比如说等式的传递性，信息的传递等。

1.查找某个元素所在的集合

经典的有： 以下数相连：1和2，2和4，4和5，4和7，5和8，6和9，6和10，问2和7之间，5和9之间是否相连？

typedef struct{ ElementType Data; int Parent; }SetType; int Find(SetType S[ ], ElementType x) { int i; for(i=0;i<MaxSize&&S[i]!= x;i++); if(i>0MaxSize) return -1; for(;S[i].Parent>=0;i=S[i].Parent); return i; }

2.集合合并

void Union(SetType S[ ],ElementType x1,ElementType x2) { int Root1,Root2; Root1 = Find(S,x1); Root2 = Find(S,x2); if(Root1 != Root2) S[Root2].Parent = Root1; }

改善性能

/*#define MAXN 1000 /* 集合最大元素个数 */ typedef int ElementType; /* 默认元素可以用非负整数表示 */ typedef int SetName; /* 默认用根结点的下标作为集合名称 */ typedef ElementType SetType[MAXN]; /* 假设集合元素下标从0开始 */ void Union( SetType S, SetName Root1, SetName Root2 ) { /* 这里默认Root1和Root2是不同集合的根结点 */ /* 保证小集合并入大集合 */ if ( S[Root2] < S[Root1] ) { /* 如果集合2比较大 */ S[Root2] += S[Root1]; /* 集合1并入集合2 */ S[Root1] = Root2; } else { /* 如果集合1比较大 */ S[Root1] += S[Root2]; /* 集合2并入集合1 */ S[Root2] = Root1; } } SetName Find( SetType S, ElementType X ) { /* 默认集合元素全部初始化为-1 */ if ( S[X] < 0 ) /* 找到集合的根 */ return X; else return S[X] = Find( S, S[X] ); /* 路径压缩 */ } */