蓝桥杯模拟赛 引爆炸弹-并查集+DFS

引爆炸弹

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

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

输入格式

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

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

数据约定：

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

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

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

输出格式

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

样例输入

5 5

00010

00010

01001

10001

01000

样例输出

2

样例的方法如下：先引手动引爆一个炸弹，红色的手动引爆，绿色的是间接引爆。

然后再手动引爆一个炸弹：

因此最少需要手动引爆两枚炸弹。

贴大佬代码:

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<vector>

#include<cstdlib>

#include<string>

#define eps 0.000000001

typedef long long ll;

typedef unsigned long long LL;

using namespace std;

const int N=+;

int m,n;

int t;

int vis[N];

struct node{

    int x,y;

}a[N];

int parent[N];

void init(){

    memset(vis,,sizeof(vis));

    for(int i=;i<=N;i++)parent[i]=i;

}

int find(int x){

    int r=x;

    while(r!=parent[r])r=parent[r];

    int i=x;

    int j;

    while(parent[i]!=r){

        j=parent[i];

        parent[i]=r;

        i=j;

    }

    return r;

}

void Union(int x,int y){

    x=find(x);

    y=find(y);

    if(x!=y)parent[x]=y;

}

void DFS(int x){

    vis[x]=;

    for(int i=;i<t;i++){

        if(vis[i]==&&(a[i].x==a[x].x||a[i].y==a[x].y)){

            Union(i,x);DFS(i);

        }

    }

}

int main(){

    char c;

    init();

    scanf("%d%d",&m,&n);

    getchar();

    t=;

    for(int i=;i<=m;i++)

    for(int j=;j<=n;j++){

        cin>>c;

        if(c==''){a[t].x=i;a[t].y=j;t++;}

    }

    for(int i=;i<t;i++)DFS(i);

    int ans=;

    for(int i=;i<t;i++){

        if(parent[i]==i)ans++;

    }

    cout<<ans<<endl;

}