DFS 에서 떨어진 연결된 부분집합 구하기

DFS 에서 ..각연결된 부분 집합을 구하는 문제가 자주 나온다 

쉽게 1 부터  max 값까지 쭉 가면서 map 을 하나 더 구해서 각각의 DFS 를 구한뒤 

연결된 부분집합의 갯수를 구하는 문제

https://www.acmicpc.net/problem/2468

#include <stdio.h>
#include <iostream> 
#include <vector>
#include <cmath>
#include <string>
#include <set>
#include <queue>
#include <functional>
#include <algorithm>
#include <memory.h>


#pragma warning(disable : 4996)
using namespace std;

long long min_v, max_v;

#define MAX(a,b) a>b ? a:b
#define MIN(a,b) a>b ? b:a


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

int input[101][101];
int map[101][101];
bool visited[101][101]; // 100x100 
int check[101][101];

int N;
int min_val = 99999999, max_val = 0;
int ans = 0;

void dbg_print(void){

	//cout << "min " << min_val << endl;
	//cout << "max " << max_val << endl;

	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			cout << map[i][j] << " ";

		}
		cout << endl;
	}
}




void dfs(int x, int y, int n) {

	visited[x][y] = true;
	check[x][y] = 1;

	for (int i = 0; i<4; i++){
		int nx = dx[i] + x, ny = dy[i] + y;

		if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] ==1 && !visited[nx][ny]){
		
			dfs(nx, ny, n);
		}
	}


	
}

void mem_reset(void){

	memset(map, 0, sizeof(map)),
	memset(visited, false, sizeof(visited));


}


int main() {

	int TC = 1;
	int V, E, S;

	int cnt;
	freopen("input5.txt", "r", stdin);	setbuf(stdout, NULL); 

	cin >> N;

	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			cin >> input[i][j];
			min_val = min(min_val, input[i][j]); 
			max_val = max(max_val, input[i][j]);

		}
	}


	for (int idx = 1; idx <= max_val; idx++){

		cnt = 0;

		mem_reset();
		for (int i = 0; i < N; i++){
			for (int j = 0; j < N; j++){
				if (input[i][j] >= idx)
					map[i][j] = 1;						
			}
		}
		
		for (int i = 0; i < N; i++){
			for (int j = 0; j < N; j++){
				if (!visited[i][j] && map[i][j]==1){
					cnt++;
					dfs(i, j, idx);

				}
			}
		}

		ans = max(ans, cnt);		
	
	}
		
	cout << ans<