質問する

グラフの隣の部分をチェックして、数えていくつかのグループがあります.
各ノードはdfsを使用して行うことができます.

code

/**
 * 백준 1012
 * DFS 문제 (또는 union-find)
 * 서로 인접해있는 그룹의 수를 구하시오.
*/
#include <bits/stdc++.h>
using namespace std;

int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};

int graph[51][51];
int m,n,k;
int ans;

void dfs(int y,int x){
    for(int i=0;i<4;i++){
        int my=y+dy[i];
        int mx=x+dx[i];

        if(my<0 or my>=m or mx<0 or mx>=n){
            continue;
        }

        else if(graph[my][mx]==1){
            graph[my][mx]=0;
            dfs(my,mx);
        }
    }
}

int main(void){
    int tc;
    cin >>tc;
    while(tc--){
        cin >>m>>n>>k;
        
        // init
        for(int i=0;i<m;i++){
            memset(&graph[i],0,sizeof(graph[i]));
        }

        for(int i=0;i<k;i++){
            int y,x;
            scanf("%d %d",&y,&x);
            graph[y][x]=1;
        }

        ans=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(graph[i][j]==1){
                    ans++;
                    graph[i][j]=0;
                    dfs(i,j);
                }
            }
        }
        cout<<ans<<endl;
    }
}