about_并查集

    前天刚学了并查集,挺好用的,虽然我现在只会用它来解决是不是亲戚啊,是不是朋友啊,带权并查集还不是很理解。

    并查集也叫做不相交集合,主要有3个操作,初始化,查找,合并。

    并查集其中一个很大的应用就是kruskal嘛。

    并查集就是说,有n个元素嘛,我们把每个元素初始化为一个集合,然后不断查找,看看是不是有关系,有的话就合并。

代码手打,无语法高亮,其实是我不知道怎么弄,囧。

const int MAXN=1000+10;//最大点数

int father[MAXN];

int rank[MAXN];//用于按秩合并,使查找速度更快

void make_set(int x)

{

  father[x]=x;

  rank[x]=0;

}

int find_set(int x)

{

  if(father[x]==x)

    return x;

  else

    return father[x]=find_set(father[x]);

}//路径压缩

void union_set(int x,int y)

{

  x=find_set(x);

  y=find_set(y);

  if(x==y)

    return ;

  if(rank[x]>rank[y])

    father[y]=x;

  else

  {

    if(rank[x]==rank[y])

      rank[y]++;

    father[x]=y;

  }

}

上一篇:Myeclipse学习总结(3)——Myeclipse中的代码格式化、注释模板及保存时自动格式化


下一篇:U盘格式化时分配单元的大小的设置