백준 1012번 파이썬 bfs

from collections import deque

t=int(input())

dx=[1,-1,0,0]

dy=[0,0,1,-1]

def bfs(graph,x,y):

    

    graph[x][y]=0

    queue=deque()

    queue.append((x,y))

    while queue:

        x,y = queue.popleft()

        for i in range(4):

            nx=x+dx[i]

            ny=y+dy[i]

            if nx>=n or nx<0 or ny<0 or ny>=m:

                 continue

            if graph[nx][ny]==1:

                queue.append((nx,ny)) 

                graph[nx][ny]=0

                

    return

for _ in range(t):

    cnt=0

    n,m,num=map(int,input().split())

    graph=[[0]*m for x in range(n)]

    for i in range(num):

        x,y=map(int,input().split())

        graph[x][y]=1

    for i in range(n):

        for j in range(m):

            if graph[i][j]:

                

                bfs(graph,i,j)

                cnt+=1

    print(cnt)