最小生成树之kruskal(并查集)---zoj_1586
????????今天细读了算法导论的21章不相交集合，也就是传说中的并查集，有点小收获。原来网上搜的并查集只介绍了路径压缩，今天第一次听说还有按秩合并这回事儿。算法导论上说，同时利用按秩合并和路径压缩技术处理，并查集的操作速度可以大大提升。设有一连串的make-set,find-set,union操作共m个，其中make-set有n个，在渐进意义上，这一连串的操作的时间复杂度为O(m*a(n))，a(n)是一个增长很慢的函数。具体证明不太懂，以后有时间再看。这里值得注意的一点就是union操作包含2个find-set操作和1个link操作。
??????? 再用并查集来分析一下kruskal算法，首先对于带权的边排序的效率为O（ElogE）,make-set操作V次,union操作E次，因此总的时间复杂度为(V+E')a(V)+O(ElogE)，a(v)=4，E'<V,总的复杂度可以简化为O(V+ElogE)=O(ElogE),换一种表示形式为O(ElogV),因为E<V*V
???????
#include<iostream>#include<algorithm>using namespace std;class union_find_set { public: const static int maximum=1001; int anc; int father[maximum]; int count[maximum]; int rank[maximum]; union_find_set() { for(int i=0;i<maximum;i++) { this->father[i]=i; this->count[i]=1; this->rank[i]=0; } } int getFather(int v) { if(father[v]==v) { return v; } else { return father[v]=getFather(father[v]); } } bool same(int x,int y) { return (getFather(x)==getFather(y)); } bool judge(int x,int y) { int fx,fy; fx=getFather(x); fy=getFather(y); if(fx==fy) return false; else { if(rank[x]<rank[y]) {father[fx]=fy; count[fy]+=count[fx]; } else if(rank[x]>rank[y]) { father[fy]=fx; count[fx]+=count[fy]; } else { father[fx]=fy; count[fy]+=count[fx];++rank[fy]; } return true; } } void init(int max) { for(int i=0;i<=max;i++) { this->father[i]=i; this->count[i]=1; this->rank[i]=0; } } };class node{public:int x,y,cost,flag;node(){flag=0;}};int cmp(const void*a,const void*b){node* A=(node*)a;node* B=(node*)b;if(A->cost>B->cost) return 1;if(A->cost<B->cost) return -1;return 0;}int main(){int n,m;while(cin>>n>>m){node p[m];for(int i=0;i<m;i++){cin>>p[i].x>>p[i].y>>p[i].cost;}qsort(p,m,sizeof(p[0]),cmp);/*for(int i=0;i<m;i++){cout<<p[i].x<<" "<<p[i].y<<" "<<p[i].cost<<endl;}*/union_find_set ufset;ufset.init(n-1);int max=0;for(int i=0;i<m;i++){if(ufset.judge(p[i].x,p[i].y)){p[i].flag=1;if(p[i].cost>max)max=p[i].cost;}}cout<<max<<endl;cout<<n-1<<endl;for(int i=0;i<m;i++){if(p[i].flag==1)cout<<p[i].x<<" "<<p[i].y<<endl;}}}?