在一个 n×m 的方格地图上，某些方格上放置着炸弹。手动引爆一个炸弹以后，炸弹会把炸弹所在的行和列上的所有炸弹引爆，被引爆的炸弹又能引爆其他炸弹，这样连锁下去。
现在为了引爆地图上的所有炸弹，需要手动引爆其中一些炸弹，为了把危险程度降到最低，请算出最少手动引爆多少个炸弹可以把地图上的所有炸弹引爆。
输入格式
第一行输两个整数 n, m，用空格隔开。
接下来 n 行，每行输入一个长度为 m 的字符串，表示地图信息。0表示没有炸弹，1表示炸弹。
数据约定：
对于60% 的数据： 1≤n,m≤100；
对于 100% 的数据： 1≤n,m≤1000；
数据量比较大，不建议用cin输入。
输出格式
输出一个整数，表示最少需要手动引爆的炸弹数。
思路：
看到题目知道要用并查集来做，但是不知道怎么去将所想思路转化为代码，网上看到程序，认真看了一遍，感觉很有收获。
#include <iostream> #include <set> using namespace std; struct node { int col; int row; } fg[1001]; //记录炸弹位置 int pre[1002]; //记录代表元 int cnt=0; int findpre(int n)//寻找该炸弹的最大boss { while(pre[n]!=n) { n=pre[n]; } return n; } void join(int n)//合并 { int c=fg[n].col,r=fg[n].row; int father=findpre(n); for(int i=0; i<cnt; i++) { if(fg[i].col==c)//同列的炸弹的最大boss指向该炸弹的最大boss { pre[findpre(i)]=father; } if(fg[i].row==r)//同行的炸弹的最大boss指向该炸弹的最大boss { pre[findpre(i)]=father; } } } int main() { char str[1002]; int n,m; cin>>n>>m; for(int i=0; i<n; i++) //n行 { cin>>str; for(int j=0; j<m; j++) //m列 { if(str[j]=='1') { fg[cnt].row=i; fg[cnt].col=j; cnt++; //记录炸弹个数 } } } for(int i=0; i<cnt; i++) pre[i]=i; //根结点初始化，第一个炸弹 for(int i=0; i<cnt; i++) { join(i); } // for(int i=0;i<cnt;i++) // cout<<"第"<<i<<"的直接boss是"<<findpre(i)<<endl; set<int> s; //set容器，自动排序，元素互不相等(若set中已有元素和新插入的元素相同，元素个数不会增加) for(int i=0; i<cnt; i++) { s.insert(findpre(i)); } cout<<s.size()<<endl; }
fg[i]记录了炸弹的位置信息(行和列)
pre[i] 记录了 炸弹(fg[i]) 的所在树的根结点
这种存储对应方式 感觉用的很好 学习一下！