寒假专题训练--并查集/生成树

并查集 生成树

地址

A - How Many Tables

[[HDU - 1213]

• 题意
  设A认识B，B认识C，则A，B，C互相是朋友，以此类推。只有互相是朋友，才可以坐在一个桌子上。求出这场宴会最少需要多少张桌子。
• 思路
  并查集。可将一个朋友圈中任何一个人指向该圈子中同一个人。若发现一个人与该朋友圈的人是朋友，那么那个人原本的朋友圈与该朋友圈合为一个圈，新圈子的每一个人都指向同一个人。最后，有多少朋友圈，就有多少个被指向的人。
• 代码

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,t,ans;
int set[1005],size[1005],flag[1005];
void build(){
  for (int i = 1; i <= n; ++i)
  {
    set[i]=i;
    size[i]=1;
  }
}
int f(int x){
  if (x==set[x])
  {
    return x;
  }else{
    set[x]=f(set[x]);
    return set[x];
  }
}
void connect(int x,int y){
  int fx,fy;
  fx=f(x);
  fy=f(y);
  if (fx==fy)
  {
    return;
  }
  if (size[fx]>=size[fy])
  {
    size[fx]+=size[fy];
    set[fy]=fx;
  }else{
    size[fy]+=size[fx];
    set[fx]=fy;
  }
}
int main(){
  scanf("%d",&t);
  while(t--){
    scanf("%d%d",&n,&m);
    build();
    ans=0;
    for (int i = 1; i <= n; ++i)
    {
      flag[i]=0;
    }
    for (int i = 1; i <= m; ++i)
    {
      int a,b;
      scanf("%d%d",&a,&b);
      connect(a,b);
    }
    for (int i = 1; i <= n; ++i)
    {
      if (flag[f(i)]==0)
      {
        flag[set[i]]=1;
        ans++;
      }
    }
    printf("%d\n",ans );
  }
  return 0;
}

B - Corporative Network

[POJ - 1962]

• 题意

• 思路

• 代码

D - 食物链

[POJ - 1182]

• 题意
  已知对第X个动物和第Y个动物有两种描述，一种是X和Y是同种动物，一种是X吃Y。同种不相食。对N个动物，连续进行多次描述。
  当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
  1） 当前的话与前面的某些真的话冲突，就是假话；
  2） 当前的话中X或Y比N大，就是假话；
  3） 当前的话表示X吃X，就是假话。
  输出假话的总数。

• 思路

• 代码

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int n,k,ans,set[150005],size[150005];
struct word{
  int d,x,y;
}w[100005];
void build(){
  for (int i = 1; i <= 3*n; ++i)
  {
    set[i]=i;
    size[i]=1;
  }
}
int f(int x){
  if (x==set[x])
  {
    return x;
  }else{
    set[x]=f(set[x]);
    return set[x];
  }
}
void connect(int x,int y){
  int fx,fy;
  fx=f(x);
  fy=f(y);
  if (fx==fy)
  {
    return;
  }
  if (size[fx]>=size[fy])
  {
    size[fx]+=size[fy];
    set[fy]=fx;
  }else{
    size[fy]+=size[fx];
    set[fx]=fy;
  }
}
int main(){
  ans=0;
  scanf("%d%d",&n,&k);
  for (int i = 0; i < k; ++i)
  {
    scanf("%d%d%d",&w[i].d,&w[i].x,&w[i].y);
  }
  build();
  for (int i = 0; i < k; ++i)
  {
    int d,x,y;
    d=w[i].d;
    x=w[i].x;
    y=w[i].y;
    if (x>n||y>n)
    {
      ans++;
      continue;
    }
    if (d==2&&x==y)
    {
      ans++;
      continue;
    }
    if (d==1)
    {
      if (f(3*x-2)==f(3*y-1)||f(3*x-1)==f(3*y)||f(3*x)==f(3*y-2)||
        f(3*y-2)==f(3*x-1)||f(3*y-1)==f(3*x)||f(3*y)==f(3*x-2))
      {
        ans++;
        continue;
      }
      connect(3*x-2,3*y-2);
      connect(3*x-1,3*y-1);
      connect(3*x,3*y);
    }else{
      if (f(3*x-2)==f(3*y-2)||f(3*x-1)==f(3*y-1)||f(3*x)==f(3*y))
      {
        ans++;
        continue;
      }
      if (f(3*y-2)==f(3*x-1)||f(3*y-1)==f(3*x)||f(3*y)==f(3*x-2))
      {
        ans++;
        continue;
      }
      connect(3*x-2,3*y-1);
      connect(3*x-1,3*y);
      connect(3*x,3*y-2);
    }
  }
  printf("%d\n",ans );
  return 0;
}