dfs bfs图

1. from collections import deque
2. n,m=map(int,input().split())
3. direction=[[0,1],[0,-1],[1,0],[-1,0]]
4. g=[]
5. for i in range(n):
6.     g.append(list(map(int,input().split())))
7. visit=[[False]*(m) for _ in range(n)]
8. res=0
9. def bfs(g,visit,x,y):
10.     deq=deque([])
11.     deq.append([x,y])
12.     visit[x][y]=True
13.     while deq:
14.         cx,cy=deq.popleft()
15.         for i,j in direction:
16.             next_x=cx+i
17.             next_y=cy+j
18.             if next_x<0 or next_x>=n or next_y<0 or next_y>=m:
19.                 continue
20.             if not visit[next_x][next_y] and g[next_x][next_y]==1:
21.                 visit[next_x][next_y]=True
22.                 deq.append([next_x,next_y])
24. for i in range(n):
25.     for j in range(m):
26.         if not visit[i][j] and g[i][j]==1:
27.             res+=1
28.             bfs(g,visit,i,j)
29. print(res)

bfs↑

dfs↓

1. n,m=map(int,input().split())
2. g=[]
3. for i in range(n):
4.     g.append(list(map(int,input().split())))
5. direction=[[0,1],[0,-1],[1,0],[-1,0]]
6. flag=[[False]*(m) for i in range(n)]
8. def dfs(g,flag,x,y):
9.     for i,j in direction:
10.         next_x=x+i
11.         next_y=y+j
12.         if x+i>n-1 or x+i<0 or y+j>m-1 or y+j<0:
13.             continue
14.         if not flag[next_x][next_y] and g[next_x][next_y]==1:
15.             flag[next_x][next_y]=True
16.             dfs(g,flag,next_x,next_y)
17. res=0
18. for i in range(n):
19.     for j in range(m):
20.         if g[i][j]==1 and not flag[i][j]:
21.             res+=1
22.             flag[i][j]=True
23.             dfs(g,flag,i,j)
24. print(res)