在一个 n \times mn×m 的方格地图上，某些方格上放置着炸弹。手动引爆一个炸弹以后，炸弹会把炸弹所在的行和列上的所有炸弹引爆，被引爆的炸弹又能引爆其他炸弹，这样连锁下去。
现在为了引爆地图上的所有炸弹，需要手动引爆其中一些炸弹，为了把危险程度降到最低，请算出最少手动引爆多少个炸弹可以把地图上的所有炸弹引爆。
输入格式
第一行输两个整数 n,mn,m，用空格隔开。
接下来 nn 行，每行输入一个长度为 mm 的字符串，表示地图信息。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
这是一道并查集的题目，需要注意要将纵坐标变化一下，进行唯一化处理，即：j变为j+n；
代码：
#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++; } int b=find(j+n); if(!vis[b]) { vis[b]=true; res++; } } } } cout<<res<<endl; }