和根植物

和根植物

题目

题目分析

矩阵上的每个节点开始BFS()如果遍历过 return没有就标记已遍历，总数+1然后从该点进行广搜如果每搜过就放入队列并标记搜过

代码

#include#include#include#include#include#include#include#define MAX 1000000+10using namespace std;vector v[MAX];int vis[MAX] = {0}; //判断是否int sum = 0; //标记有多少个植物int m,n;void BFS(int row,int col);int main(){ //数据输入 //freopen("in.txt","r",stdin); cin >> m >> n; int num; cin >> num; for(int i = 0;i < num;i++) { int a,b; cin >> a >> b; v[a].push_back(b); v[b].push_back(a); } for(int i = 1;i <=m ;i++ )//行 { for(int j = 1;j <= n;j++) //列 { BFS(i,j); } } cout << sum << endl;}void BFS(int row,int col){ int top = (row-1)*n+col; if(vis[top]==1) return ; queue q; q.push(top); vis[1] = 1; sum++; while(!q.empty()) { int temp = q.front(); q.pop(); int size = v[temp].size(); for(int i = 0;i < size;i++) { int top1 = v[temp][i];//表示的当前的找的节点 if(vis[top1]==0) { vis[top1] = 1; q.push(top1); } } }}/* 一个节点进行广搜 终止了继续下一个寻找下一个节点 判断的过程 搜的过程 搜过跳过。 没搜过标记*/

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。