poj-2236 Wireless Network &&poj-1611 The Suspects && poj-2524 Ubiquitous Religions (基础并查集）

http://poj.org/problem?id=2236

由于发生了地震，有关组织组把一圈电脑一个无线网，但是由于余震的破坏，所有的电脑都被损坏，随着电脑一个个被修好，无线网也逐步恢复工作，但是由于硬件的限制，一台电脑和另一台电脑能够相连当他们之间的距离小于d，或者还有一台电脑当中介，分别与两台电脑相连。

在修复的过程中，工作者会有两种操作，修复电脑和询问电脑a和电脑b是否相连。当询问的时候输出答案。

因为输入数据很大，需要快速判断电脑a和电脑b相连，所以自然想到用并查集。

初始时候 全部电脑都是损坏的，那么每修复一次，就需要把与当前电脑距离小于d并且已经修复的电脑连接起来，询问的时候直接判断即可。

#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn = 1010;
struct node
{
    int x,y;
}p[maxn];
int par[maxn],flag[maxn];  //作为是否修复的标记
int n;
double dis[maxn][maxn];  //存储两点之间的距离
double d;
void init()
{
    for(int i=1;i<=n;i++) par[i]=i;
}

int find(int x)
{
    return x==par[x]?x:par[x]=find(par[x]);
}

void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y)
        par[x]=y;
}

void distance(int a,int b)
{
    dis[a][b]=dis[b][a]=sqrt(1.0*(p[a].x-p[b].x)*(p[a].x-p[b].x)+1.0*(p[a].y-p[b].y)*(p[a].y-p[b].y));
}

void solve(int x)
{
    for(int i=1;i<=n;i++)
    {
        if(i!=x&&flag[i]&&dis[x][i]<=d)
            unite(x,i);
    }
}

int main()
{
   //freopen("a.txt","r",stdin);
    scanf("%d%lf",&n,&d);
    init();
    memset(flag,0,sizeof(flag));
    memset(dis,0,sizeof(dis));
    for(int i=1;i<=n;i++)
        scanf("%d%d",&p[i].x,&p[i].y);
    for(int i=1;i<=n;i++)   //预处理所有两点之间的距离
        for(int j=i+1;j<=n;j++)
        distance(i,j);
    char s[2];
    int a,b;
    while(~scanf("%s",s))
    {
        if(s[0]=='O')
        {
            scanf("%d",&a);
            flag[a]=1;
            solve(a);
        }
        else if(s[0]=='S')
        {
            scanf("%d%d",&a,&b);
            if(find(a)==find(b)) printf("SUCCESS
");
            else printf("FAIL
");
        }
    }
    return 0;
}

 http://poj.org/problem?id=1611

 在大学里有n个学生(0-n-1)和m个社团，每个学生可以加多个社团，但是因为SARS的流行，学校需要统计出有多少病毒携带者，如果一个社团有一个携带者，那么整个社团都是  病毒携带者，现在已知0号学生是携带者，给出m个社团的信息，求出有多少人感染。

 基础的并查集，只要增加一个rank[]用来统计每一个组的人数，这样在unite的时候累加合并过来的人数，最后输出0号所在的组的人数。

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 30010;
int par[maxn],rank[maxn];

void init(int n)
{
    for(int i=0;i<n;i++)
    {
        par[i]=i;
        rank[i]=1;
    }
}

int find(int x)
{
    return x==par[x]?x:par[x]=find(par[x]);
}

void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y)
    {
        par[x]=y;
        rank[y]+=rank[x];
    }
}

int main()
{
    int n,m,k,a,b;
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0) break;
        init(n);
        for(int i=0;i<m;i++)
        {
            scanf("%d",&k);
            for(int j=0;j<k;j++)
            {
                scanf("%d",&a);
                if(j==0)
                {
                    b=a;
                }
                else unite(a,b);
            }
        }
        printf("%d
",rank[find(0)]);
    }
    return 0;
}

http://poj.org/problem?id=2524

n个学生，每个学生都只有一种信仰，给出m条关系，统计最多有多少种信仰。

简单并查集，读入关系后合并即可。

#include <cstdio>
const int maxn = 50010;
int n,count,par[maxn];

void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        par[i]=i;
    }
}

int find(int x)
{
    return x==par[x]?x:par[x]=find(par[x]);
}

void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y)
    {
        par[x]=y;
        count--;
    }
}

int main()
{
    int m,a,b,j=1;
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0) break;
        count=n;
        init(n);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            unite(a,b);
        }
        printf("Case %d: %d
",j++,count);
    }
    return 0;
}