并查集

引爆炸弹：

题目描述：
在一个$n \times n $的方格地图上，某些方格上放置着炸弹。手动引爆一个炸弹以后，炸弹会把炸弹所在的行和列上的所有炸弹引爆，被引爆的炸弹又能引爆其他炸弹，这样连锁下去。

现在为了引爆地图上的所有炸弹，需要手动引爆其中一些炸弹，为了把危险程度降到最低，请算出最少手动引爆多少个炸弹可以把地图上的所有炸弹引爆。

输入格式
第一行输两个整数 n,m，用空格隔开。

接下来 n 行，每行输入一个长度为 m 的字符串，表示地图信息。0表示没有炸弹，1表示炸弹。

数据约定：

对于 60%60% 的数据：1 \le n, m \le 1001≤n,m≤100；

对于 100%100% 的数据：1 \le n, m \le 10001≤n,m≤1000；

数据量比较大，不建议用cin输入。

输出格式
输出一个整数，表示最少需要手动引爆的炸弹数。

此题为并查集，进行归一化处理，将行数与列数看做一种数，所有的炸弹只要行数或列数有一个相同就会归为一个集合，只有行数、列数都不同的炸弹才属于新的集合。只需遍历所有炸弹位置，统计有多少炸弹集合。

样例输入：
5 5
00010

00010

01001

10001

01000

输出：2

代码：

c++

#include<iostream>
#include<string.h>
#define maxn 10010
using namespace std;
char map[10010][10010];
bool vis[10010]={false};
int pre[10010];
int num=0;
void init()
{
    for(int i=0;i<maxn;i++)
    {
        pre[i]=i;
    }
}
int find(int x)
{
    int a=x;
    while(x!=pre[x])
    {
        x=pre[x];
    }
    while(a!=pre[a])
    {
        int z=a;
        a=pre[a];
        pre[z]=x;
    }
    return x;
}
void Union(int a,int b)
{
    int Fa=find(a);
    int Fb=find(b);
    if(Fa!=Fb)
    pre[Fa]=Fb;
}
int main()
{
    int n,m;
    int k;
     scanf("%d%d",&n,&m);
    init();
    for(int i = 0;i < n;i++) 
        scanf("%s",map[i]);
    
    for(int i = 0;i < n;i++)
        for(int j = 0;j < m;j++) {
            if(map[i][j]=='1') {
                Union(i,j+n);
                // cout<<i<<" "<<j<<" "<<pre[i]<<endl;
            }
        }
    int res=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(map[i][j]=='1')
            {
               int a=find(i);
                if(!vis[a])
                {
                    vis[a]=true;
                    res++;
                }
            }
        }
    }
    cout<<res<<endl; 
}

POJ 1182食物链
题目：
动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。

现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这N个动物所构成的食物链关系进行描述：

第一种说法是”1 X Y”，表示X和Y是同类。

第二种说法是”2 X Y”，表示X吃Y。

此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1）当前的话与前面的某些真的话冲突，就是假话；
2）当前的话中X或Y比N大，就是假话；
3）当前的话表示X吃X，就是假话。
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。

输入：
100 7

1 101 1

2 1 2

2 2 3

2 3 3

1 1 3

2 3 1

1 5 5

输出：
3

此题需明白的点为如果现在的说法与之前矛盾则为假话，因而将一开始最初说的话进行Union，然后每次添加新的情况时都要先进行判断，再进行添加。

代码：

c++

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
using namespace std;
int pre[150014];
int finda(int a)
{
    int x=a;
    while(pre[x]!=x)
    {
        x=pre[x];
    }
    return x;
}
bool same(int n,int m)
{
    return finda(n)==finda(m);
}
void merge(int x,int y)
{
      int f1=finda(x);
      int f2=finda(y);
      if(f1!=f2)
       pre[f1]=f2;
}
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n*3;i++)
        pre[i]=i;
    int a[100005],b[100005],c[100005];
    int num=0;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
        int x=b[i]-1;
        int y=c[i]-1;
        if(x<0||x>=n||y<0||y>=n)
        {
            num++;
            continue;
        }
        if(a[i]==1)
        {
            if(same(x,y+n)||same(x,y+2*n))
                num++;
            else 
            {
                merge(x,y);
                merge(x+n,y+n);
                merge(x+2*n,y+2*n);
            }
        }
        else 
        if(a[i]==2)
        {
            if(same(x,y)||same(x,y+2*n))
                num++;
            else 
            {
                merge(x,y+n);
                merge(x+n,y+2*n);
                merge(x+2*n,y);
            }
        }
            
    }
    printf("%d\n",num);
    return 0;
}