计蒜客引爆炸弹（DFS、并查集）

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

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

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

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

数据约定：

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

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

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

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

样例输入

样例输出

方法一（DFS）：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <sstream>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9+7;
16 const double PI = acos(-1);
17 const double eps =1e-8;
18 #define Bug cout<<"---------------------"<<endl
19 const int maxn=1e5+10;
20 using namespace std;
21 
22 char G[1005][1005];
23 int n,m,ans; 
24 int vx[1005],vy[1005];//vx[i]表示第i行有没有引爆过，vy[i]表示第i列有没有引爆过 
25 
26 void DFS(int x,int y)
27 {
28     G[x][y]='0';
29     if(!vx[x])
30     {
31         vx[x]=1;
32         for(int i=1;i<=m;i++)
33         {
34             if(G[x][i]=='1')
35                 DFS(x,i);
36         }
37     }
38     if(!vy[y])
39     {
40         vy[y]=1;
41         for(int i=1;i<=n;i++)
42         {
43             if(G[i][y]=='1')
44                 DFS(i,y);
45         }
46     }
47 }
48 
49 int main()
50 {
51     #ifdef DEBUG
52     freopen("sample.txt","r",stdin);
53     #endif
54     ios_base::sync_with_stdio(false);
55     cin.tie(NULL);
56     
57     scanf("%d %d",&n,&m);
58     for(int i=1;i<=n;i++)
59         scanf("%s",G[i]);
60     for(int i=1;i<=n;i++)
61     {
62         for(int j=1;j<=m;j++)
63         {
64             if(G[i][j]=='1')
65             {
66                 DFS(i,j);
67                 ans++;
68             }
69         }
70     }
71     printf("%d
",ans);
72     return 0;
73 }

方法二（并查集）：

使用并查集相较DFS比较麻烦，类比连通块，将相互联通的炸弹划到同一个集合。

这里的思路是将行列存到同一个数组中，将某一个炸弹的行列划分到一个集合，将同一行或者同一列划分到同一集合，最后存在多少个集合即为结果。

计蒜客 引爆炸弹（DFS、并查集）

计蒜客引爆炸弹（DFS、并查集）