ACM

J-并查集(Wireless Network POJ-2236)

题意：

• 首先给出一些坏电脑的坐标（点），然后给出两种操作：

  $1、$ 、修复编号为$p$的电脑；

  $2$ 、 查询编号为$p$ 、$q$ 电脑是否有联系。

  关于两台电脑的联系：

  $1$、如果编号为$A$电脑已被修复，编号为$B$的电脑也被修复，且它们的距离小于D；

  $2$、若编号为$A$的电脑与编号为$B$的电脑有联系，编号为$B$的电脑与编号为$C$的电脑有联系，则编号为$A$的电脑与编号为 $C$的有联系(传递性)；

解题思路：

• 对于判断编号为$A$的电脑是否被修复，可以用一个数组去标记一下，其它的就是一些并查集的基本操作；
• 当一个电脑被修复后，就遍历所有电脑，从中找出与它距离小于D且也被修复的电脑，然后用并查集合并到一个集合；
• 最后查询的时候就直接查询那两台电脑是否在一个集合中即可。

代码：

//#include<bits/stdc++.h>//因为POJ不支持万能表头 所以只能注释掉自己打所需要的函数库
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stdio.h>
#include<string.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e4+5;
const double eps=1e-4;
int fa[N];
void init(int n)//初始化fa数组
{
    for(int i=1;i<=n;i++)
        fa[i]=i;
}
int findd(int x)
{
    if(x==fa[x])
        return x;
    else
    {
        return fa[x]=findd(fa[x]);
    }
}
bool Union(int x,int y)
{
    int fx=findd(x),fy=findd(y);
    if(fx==fy)
        return false;
    else
    {
        fa[fx]=fy;
        return true;
    }
}
struct point
{
    int x,y;
}p[N];
int k;
int check(int a,int b)
{
    return hypot(p[a].x-p[b].x,p[a].y-p[b].y)<=k;//hypot(a,b)返回的是以a，b为边的三角形的腰长，所以根据勾股定理这里可以用来算两点距离，但注意返回的是类型double。
}
int vis[N];
int main()
{
    int n;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&p[i].x,&p[i].y);
    char s[2];
    init(n);
    while(~scanf("%s",s))
    {
        int a,b;
        if(s[0]=='O')
        {
            scanf("%d",&a);
            vis[a]=1;
            for(int i=1;i<=n;i++)
            {
                if(vis[i]==1&&a!=i&&check(a,i))//判断是否被修复，该点不能是自身，与它相距小于D
                {
                    Union(a,i);
                }
            }
        }
        else
        {
            scanf("%d%d",&a,&b);
            if(findd(a)==findd(b))
                printf("SUCCESS\n");
            else
                printf("FAIL\n");
        }
    }
    return 0;
}

K-并查集(Ubiquitous Religions POJ-2524)

题意：

• 有$N$个学生，$M$个操作，每次操作都会使两个学生的信仰的宗教变为同一个，最后问经历过$M$次操作后，那些学生信仰的宗教种类为多少？

解题思路：

• 可以理解为一开始他们分别信仰有$N$个不同的宗教种类，每操作(合并)一次都可能会使宗教种类减一，最后判断的时候就判定他当前信仰的宗教是否与他原来的宗教相同，如果是种类就加一，不是则跳过。

代码：

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stdio.h>
#include<string.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=5e4+5;
const double eps=1e-4;
int fa[N];
void init(int n)
{
    for(int i=1;i<=n;i++)
        fa[i]=i;
}
int findd(int x)
{
    if(x==fa[x])
        return x;
    else
    {
        return fa[x]=findd(fa[x]);
    }
}
bool Union(int x,int y)
{
    int fx=findd(x),fy=findd(y);
    if(fx==fy)
        return false;
    else
    {
        fa[fx]=fy;
        return true;
    }
}
int main()
{
    int cas=1;
    int n,m;
    while(~scanf("%d%d",&n,&m))//注意多组输入
    {
        if(n==0&&m==0)//终止输入的条件
            break;
        init(n);
        for(int i=0;i<m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            Union(a,b);
        }
        int ans=0;
        for(int i=0;i<n;i++)
        {
            if(fa[i]==i)//判断他当前信仰的宗教是否与原来的相同
                ans++;
        }
        printf("Case %d: %d\n",cas++,ans);//注意输出不要漏掉Case
    }
    return 0;
}

L-并查集(A Bug`s Life POJ-2492)

题意：

• 有$N$个昆虫，给你$M$个这些昆虫的恋爱关系，最后问这些昆虫的是否可能有同性恋，即它们的性别是否有矛盾？

解题思路：

• 关于是否有矛盾则可以解释为：$A$与$B$相恋，$A$与$C$相恋，而$B$与$C$也相恋，若确定$A$和$B$的性别，则根据给出的恋爱关系可知C的性别有矛盾。
• 所以我们可以设$A+N$为$A$的“矛盾面”，即与$A$与$A+N$是正常情况下是不会在一个集合，所以我们每次合并的时候都合并对方的矛盾面，即若$A$与$B$合并，则$A$合并$B$的矛盾面$B+N$,$B$合并$A$的矛盾面$A+N$,然后每次合并完后就判断它们是否与自己的矛盾面在同一个集合中，若在就标记一下。最后根据标记来输出答案。

代码：

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stdio.h>
#include<string.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=2e4+5;
const double eps=1e-4;
int fa[N];
void init(int n)
{
    for(int i=1;i<=n;i++)
        fa[i]=i;
}
int findd(int x)
{
    if(x==fa[x])
        return x;
    else
    {
        return fa[x]=findd(fa[x]);
    }
}
bool Union(int x,int y)
{
    int fx=findd(x),fy=findd(y);
    if(fx==fy)
        return false;
    else
    {
        fa[fx]=fy;
        return true;
    }
}
int main()
{
    int cas=1;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        init(2*n);//注意因为有矛盾面的存在，所以fa数组要舒适化两倍。
        int vis=0;//标记
        for(int i=0;i<m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            Union(a,b+n);//与对面矛盾面结合
            Union(b,a+n);
            if(findd(a)==findd(a+n)||findd(b)==findd(b+n))//判断是否与自己的矛盾面在相同集合
            {
                vis=1;
            }
        }
        printf("Scenario #%d:\n",cas++);
        if(vis==1)
            printf("Suspicious bugs found!\n");
        else
            printf("No suspicious bugs found!\n");
        printf("\n");
    }
    return 0;
}