程序设计竞赛模板之并查集

原理:

所有元素看成一个点,两个元素属于一个集合则把他们连边,从而形成一棵树。通过查询两个元素的根结点是否一致,来判断这两个元素是否属于同一个集合。

代码如下:

  int par[MAX_N];
  int ranks[MAX_N];
  void init(int n)
  {
    for(int i=0;i<n;i++)
    {
      par[i]=i;
      ranks[i]=0;
    }
  }
  int find(int x)
  {
    if(par[x]==x)
    {
      return x;
    }
    else
    {
      return par[x]=find(par[x]);
    }
  }
  void unite(int x,int y)
  {
    x=find(x);
    y=find(y);
    if(x==y)return;
    if(ranks[x]<ranks[y])
    {
      par[x]=y;
    }
    else
    {
      par[y]=x;
      if(ranks[x]==ranks[y])ranks[x]++;
    }
  }
  bool same(int x,int y)
  {
    return find(x)==find(y);
  }

发表评论

电子邮件地址不会被公开。 必填项已用*标注