博文

并查集的应用PKU1703(2008-08-21 13:13:00)

摘要：///////////////////////////////////////////作品名称:并查集应用//作者姓名:满天飞//作品时间:2008-8-15//最后修改:2008-8-15//Q Q 号码:280282813//版权所有,翻版必究/////////////////////////////////////////#include<stdio.h>#define MAX 100010int ary[MAX];int opt[MAX];void Init(int n){    int i;    for(i = 0; i <= n+10; ++i)    {        ary[i] = -1;        opt[i] = -1;    }}int Find(int index){    if(ary[index] < 0)        return index;    return ary[index] = Find(ary[index]);}int Union(int first, int second){    int i, j;    if(second == -1)        return first;    i = Find(first);    j = Find(second);    if(i == j)        return i;    if(ary[i] < ary[j])    {   &......

阅读全文(6141) | 评论:0

并查集的应用PKU2524(2008-08-21 13:12:00)

摘要：///////////////////////////////////////////作品名称:并查集应用//作者姓名:满天飞//作品时间:2008-8-15//最后修改:2008-8-15//Q Q 号码:280282813//版权所有,翻版必究/////////////////////////////////////////#include<iostream>using namespace std;class Set{    private:        int* ary;        int length;    public:        int Find(int index);        bool Union(int first, int second);        Set(int n);        int Count();        virtual ~Set(){delete[]ary;}};int Set::Count(){    int i, ct;    ct = 0;    for(i = 1; i <= length; ++i)    {        if(ary[i] < 0)            ct++;    }    return ct;}Set::Set(int n){ &nbs......

阅读全文(6392) | 评论:0

并查集的应用PKU2492(2008-08-21 13:11:00)

摘要：///////////////////////////////////////////作品名称:并查集应用//作者姓名:梁岳传//作品时间:2008-8-15//最后修改:2008-8-15//Q Q 号码:280282813//版权所有,翻版必究/////////////////////////////////////////#include<iostream>using namespace std;#define MAX 1000010int ary[MAX];int opt[MAX];void Init(int n){    int i;    for(i = 0; i <= n+10; ++i)    {        ary[i] = -1;        opt[i] = -1;    }}int Find(int index){    if(ary[index] < 0)        return index;    return ary[index] = Find(ary[index]);}int Union(int first, int second){    int i, j;    if(second == -1)        return first;    i = Find(first);    j = Find(second);    if(i == j)        return i;    if(ary[i] < ary[j])  ......

阅读全文(4313) | 评论:0

并查集的应用PKU2236(2008-08-21 13:10:00)

摘要：///////////////////////////////////////////作品名称:并查集应用//作者姓名:梁岳传//作品时间:2008-8-16//最后修改:2008-8-16//Q Q 号码:280282813//版权所有,翻版必究////////////////////////////////////////#include<iostream>#include<cmath>using namespace std;typedef struct{    int x;    int y;    int parent;}Node;class Set{    public:        Node* ary;        int length;    public:        int Find(int index);        bool Union(int first, int second);        Set(int n);        virtual ~Set(){delete[]ary;}};Set::Set(int n){    int i;    ary = new Node[n+10];    length = n;    for(i = 1; i <= n; ++i)    {        cin>>ary[i].x>>ary[i].y;   &......

阅读全文(6810) | 评论:0

并查集的实现及应用:最小生成树(2008-08-15 10:40:00)

摘要：///////////////////////////////////////// //作品名称:并查集的实现及应用 //作者姓名:梁岳传//作品时间:2008-8-15//最后修改:2008-8-15 //Q Q 号码:280282813 //版权所有,翻版必究 ///////////////////////////////////////// #include<iostream> using namespace std; class Set{private: int* ary; int length;public: int Find(int index); bool Union(int first, int second); Set(int n); virtual ~Set(){delete[]ary;} }; Set::Set(int n){ int i; ary = new int[n]; length = n; for(i = 0; i < n; ++i)  ary[i] = -1;} //将每次查找过的路线上的结点全部都指向根结点int Set::Find(int index){ int i, j, t;  if(index < 0 || index >= length) return -1;  //查找index元素的根结点 for(i = index; ary[i] >= 0; i = ary[i]); //将这条路线上的所有元素全部指向根结点 for(j = index; j != i; j = t){  t = ary[j];  ary[j] = i; }  return i;} //树的根结点保存树的元素个数,以负值的形式保存bool Set::Union(int first, int second){ int i, j; if(first < 0 || first >= length)  re......

阅读全文(5759) | 评论:1