最小生成树之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;
		}
	}
}