dfs：
1.从图上任意一个点u开始遍历，标记u已经被搜索过
2.递归点u的所有符合连通条件的邻居点
3.递归结束，找到了与点u联通的所有点，这是一个连通块
4.不与点u联通的，其他没有访问的点，继续用上述步骤处理，知道找到所有的连通块
#include<iostream> #include<cstring> #include<algorithm> using namespace std ; const int N = 2000 ; int d[4][2] = {{0,1},{1,0},{0,-1},{-1,0}} ; char mp[N][N] ; int v[N][N]; int flag ,ans ; void dfs(int x,int y){ v[x][y] = 1 ; if(mp[x+1][y] == '#'&&mp[x-1][y] == '#'&&mp[x][y+1] == '#'&&mp[x][y-1] == '#') flag = 1 ;//这个连通块可以不被淹没 for(int i = 0 ; i< 4 ; i++){ int tx = x + d[i][0] , ty = y + d[i][1] ; if(v[tx][ty] == 0 && mp[tx][ty] == '#'){//两个条件一个都不能少，如果不判断v那将进入死循环 dfs(tx,ty) ; } } } int main(){ int n ; cin >> n ; for(int i = 0 ; i < n ; i ++) cin >> mp[i] ; //每一个点进入循环 for(int i = 0 ; i < n ; i ++){ for(int j = 0 ; j < n ; j ++){ if(mp[i][j] == '#' && v[i][j] == 0) { flag = 0 ; dfs(i,j) ; if(!flag) ans ++ ; } } } cout << ans << endl ; return 0 ; }
bfs：
1.从图上任意一个点u开始遍历，把它放进队列中
2.弹出对手u，标记点u已经被搜索过，然后搜索点u的邻居点，即与点u连通的点，将其放到队列中
3.弹出队首，标记为已经被搜索过，然后搜索与他连通的邻居点，放进队列
继续以上步骤，直到队列为空，此时已经找到了一个连通块。其他没有访问到的点，属于另外的连通块，按以上步骤再次处理这些点。最后所有点都被搜索过，所有连通块都找到了。
#include<iostream> #include<algorithm> #include<cstring> #include<queue> using namespace std ; const int N = 2000 ; int d[4][2] = {{0,1},{1,0},{-1,0},{0,-1}} ; bool v[N][N] ; char mp[N][N] ; int flag , ans ; void bfs(int x, int y){ v[x][y] = 1 ; pair<int,int> a = {x,y} ; queue<pair<int,int>> q ;q.push(a) ; while(!q.empty()){ pair<int,int> now = q.front() ; q.pop() ; int x1 = now.first , y1 = now.second ; if(mp[x1+1][y1] == '#' &&mp[x1-1][y1] == '#' &&mp[x1][y1+1] == '#' &&mp[x1][y1-1] == '#' ) flag = 1 ; for(int i = 0 ; i < 4 ; i ++){ int tx = now.first + d[i][0] , ty = now.second + d[i][1] ; if(v[tx][ty]==0 && mp[tx][ty] =='#') { bfs(tx,ty) ; } } } } int main(){ int n; cin >> n ; for(int i = 0 ; i < n ; i ++) cin >> mp[i] ; for(int i = 0 ; i < n ; i ++){ for(int j = 0 ; j < n ;j ++){ if(v[i][j] == 0 && mp[i][j] == '#') { flag = 0 ; bfs(i,j) ; if(!flag) ans ++ ; } } } cout << ans << endl ; }
