무르르릉

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

2
2
0 0
1000 0
1000 1000
2000 1000
2
0 0
1000 0
2000 1000
2000 2000

happy
sad

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

#define MAX 102

vector<int> graph[MAX];
bool visited[MAX];

// 초기화 함수
void Init()
{
	memset(visited, false, sizeof(visited));
	for (int i = 0; i < MAX; i++)
	{
		graph[i].clear();
	}
}

// 위치간 거리 반환하는 함수
int GetDistance(pair<int, int> p1, pair<int, int> p2)
{
	return abs(p1.first - p2.first) + abs(p1.second - p2.second);
}

void Dfs(int v)
{
	visited[v] = true;
	for (int i = 0; i < graph[v].size(); i++)
	{
		int next = graph[v][i];
		if (!visited[next])
			Dfs(next);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int T;
	cin >> T;

	while(T--)
	{
		Init();

		int n;
		vector<pair<int, int>> vec;
		cin >> n;

		for (int i = 0; i < n+2; i++)
		{
			int x, y;
			cin >> x >> y;
			vec.push_back({ x, y });
		}

		// 거리가 1000 이하일 경우 위치 연결
		for (int i = 0; i < n+2; i++)
		{
			for (int j = i+1; j < n+2; j++)
			{
				int dis = GetDistance(vec[i], vec[j]);
				if (dis <= 50 * 20)
				{
					graph[i].push_back(j);
					graph[j].push_back(i);
				}
			}
		}

		Dfs(0);	// 집부터 탐색하기

		// 도착했으면 happy, 아니면 sad
		if (visited[n+1])
			cout << "happy\n";
		else
			cout << "sad\n";

	}

	return 0;
}

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

5 7
0 0 0 0 0 0 0
0 2 4 5 3 0 0
0 3 0 2 5 2 0
0 7 6 2 4 0 0
0 0 0 0 0 0 0

2

풀이

• 2차원 배열을 탐색하기 위해 BFS를 사용하였다.
• 빙산이 분리되었다 -> BFS가 2회 이상 실행되었을 때를 뜻한다. 이 경우 반복문을 탈출하여 분리됐을 때의 년수를 출력한다.
• 원래는 빙산 배열을 복사하지 않고 녹여줬었는데, 빙산이 모두 녹아 바다가 되어버려 인접한 바다의 수가 증가하는 일이 발생하여 현재 상태의 빙산 배열을 따로 복사하여 바다를 탐색하였다.
• MeltIceberg(): 만약 빙산이 분리되지 않았다면 빙산 주변에 바다가 몇 개 있는지 확인해야한다. 바다의 수만큼 빙산을 녹여주고 년수를 증가시킨다. 빙산은 음수가 될 수 없기 때문에 0 이하가 될 경우 0으로 변경해주는 조건문을 추가하였다.

void MeltIceberg()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			int cnt = 0;
			if (copyMap[i][j] == 0) continue;
			if (copyMap[i + 1][j] == 0) cnt++;
			if (copyMap[i - 1][j] == 0) cnt++;
			if (copyMap[i][j + 1] == 0) cnt++;
			if (copyMap[i][j - 1] == 0) cnt++;

			map[i][j] = map[i][j] - cnt;
			if (map[i][j] < 0) map[i][j] = 0;
		}
	}
	year++;
}

• HasAllMelt(): 분리되지 않은 채 빙산이 모두 녹았을 경우(전부 0이 되었을 때) while문을 탈출하기 위해 사용된다.

bool HasAllMelt()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (map[i][j] != 0) return false;
		}
	}
	return true;
}

전체 코드

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

#define MAX 301
#define _X first
#define _Y second

int map[MAX][MAX];
int copyMap[MAX][MAX];	// 현재 배열을 저장하여 빙산을 녹일 때 사용
bool visited[MAX][MAX];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

int N, M, year;
bool isSeparated = false;

queue<pair<int, int>> q;

void Bfs()
{
	while (!q.empty())
	{
		auto cur = q.front();
		int x = cur._X;
		int y = cur._Y;
		q.pop();

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

			if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
			if (map[nx][ny] == 0 || visited[nx][ny]) continue;
			q.push({ nx, ny });
			visited[nx][ny] = true;
		}
	}
}

// 빙산이 다 녹았으면 참, 아니면 거짓 반환하는 함수
bool HasAllMelt()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (map[i][j] != 0) return false;
		}
	}
	return true;
}

// 빙산을 녹이는 함수
// 빙산이 존재하는 위치의 상하좌우를 탐색하여 주변 바다의 수를 저장하여 녹이고, 년수를 증가시킨다
void MeltIceberg()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			int cnt = 0;
			if (copyMap[i][j] == 0) continue;
			if (copyMap[i + 1][j] == 0) cnt++;
			if (copyMap[i - 1][j] == 0) cnt++;
			if (copyMap[i][j + 1] == 0) cnt++;
			if (copyMap[i][j - 1] == 0) cnt++;

			map[i][j] = map[i][j] - cnt;
			if (map[i][j] < 0) map[i][j] = 0;
		}
	}
	year++;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> map[i][j];
		}
	}

	while (true)
	{
		if (HasAllMelt()) break;

		int cnt = 0;
		
		memset(visited, false, sizeof(visited));

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				if (map[i][j] > 0 && !visited[i][j])
				{
					visited[i][j] = true;
					q.push({ i, j });
					Bfs();
					cnt++;
				}
				copyMap[i][j] = map[i][j];	// 현재 배열 저장
			}
		}

		if (cnt > 1)
		{
			isSeparated = true;
			break;
		}

		MeltIceberg();
	}

	if (isSeparated)
		cout << year;
	else
		cout << 0;

	return 0;
}

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

문제

N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

<그림 1>

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

<그림 2>

<그림 3>

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

8 9
0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0
0 0 0 1 1 0 1 1 0
0 0 1 1 1 1 1 1 0
0 0 1 1 1 1 1 0 0
0 0 1 1 0 1 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

4

풀이

• 백준 2636 치즈(hhttps://www.acmicpc.net/problem/2636)와 유사한 문제로 치즈를 녹이기 위한 조건이 하나 추가된 문제이다.
• 바깥쪽에 있는 치즈 중 공기와 맞닿은 곳이 두면 이상일 경우 녹여줘야하기 때문에 2차원 배열에 존재하는 모든 공기를 2로 변경하여 치즈와 맞닿은 면을 체크하고, 치즈 주변에 있는 공기면의 수를 체크하여 녹여준다.
• 배열을 계속 탐색해야 하기 때문에 2로 변경했던 외부 공기를 다시 0으로 되돌린다.
• 배열에 치즈 존재하지 않을 때까지 BFS를 실행하여 녹는 시간을 증가시킨다.

전체 코드

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

#define MAX 101
#define _X first
#define _Y second

int board[MAX][MAX];
bool visited[MAX][MAX];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

int N, M, hour;

queue<pair<int, int>> q;

// 2로 변경한 외부 공기를 다시 0으로 바꿔주는 함수
void ResetAir()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (board[i][j] == 2)
				board[i][j] = 0;
		}
	}
}

// 배열에 치즈가 존재하지 않을 경우 true, 존재할 경우 false 반환
bool HasAllMelted()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (board[i][j] != 0)
				return false;
		}
	}
	return true;

}

// 치즈 사방에 공기가 있을 경우 카운트 증가시킨 후, 두면이 공기라면 치즈를 녹임
void MeltCheese()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			int airCount = 0;
			if (board[i][j] != 1) continue;
			if (board[i + 1][j] == 2) airCount++;
			if (board[i - 1][j] == 2) airCount++;
			if (board[i][j + 1] == 2) airCount++;
			if (board[i][j - 1] == 2) airCount++;

			if (airCount >= 2)
			{
				board[i][j] = 0;
			}
		}
	}
}

void Bfs()
{
	q.push({ 0, 0 });
	visited[0][0] = true;
	hour++;

	while (!q.empty())
	{
		pair<int, int> cur = q.front();
		int x = cur._X;
		int y = cur._Y;
		q.pop();

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

			if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
			if (board[nx][ny] != 0 || visited[nx][ny]) continue;
			// 공기를 2로 바꿔줌
			q.push({ nx, ny });
			board[nx][ny] = 2;
			visited[nx][ny] = true;
		}
	}
}


int main()
{
	cin.tie(0); cout.tie(0);

	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> board[i][j];
		}
	}

	while (true)
	{
		if (HasAllMelted())
		{
			cout << hour;
			break;
		}

		memset(visited, 0, sizeof(visited));
		Bfs();
		MeltCheese();
		ResetAir();
	}

	return 0;
}

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

문제

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

<그림 1> 원래 치즈 모양

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

<그림 2> 한 시간 후의 치즈 모양

<그림 3> 두 시간 후의 치즈 모양

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

풀이

• 치즈가 다 없어질 때까지 BFS를 실행하는 문제이다.
• 바깥쪽에 있는 치즈만 찾아내면 되기 때문에 (0, 0) 좌표부터 차례대로 탐색하고 사방에 치즈가 있을 경우 녹여준다.
• 모두 녹기 한 시간 전에 남아있는 치즈 개수를 확인하기 위해서 BFS를 실행할 때마다 현재 남은 치즈의 개수를 temp 변수에 저장해둔다.

코드

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

#define MAX 101
#define _X first
#define _Y second

int board[MAX][MAX];
bool visited[MAX][MAX];
int n, m, hour, temp;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
bool check = false;

queue<pair<int, int>> q;

void Bfs()
{
	q.push({ 0, 0 });
	visited[0][0] = true;
	hour++;
	int cnt = 0;
	while (!q.empty())
	{
		pair<int, int> cur = q.front();
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = cur._X + dx[i];
			int ny = cur._Y + dy[i];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (visited[nx][ny]) continue;
			if (board[nx][ny] == 0)
			{
				q.push({ nx, ny });
			}
			// 치즈 있으면 녹여주고 치즈 개수 증가
			else
			{
				board[nx][ny] = 0;
				cnt++;
			}
			visited[nx][ny] = true;
		}
	}

	if (cnt == 0)
		check = true;
	//  치즈가 남았다면 현재 남은 치즈 저장
	else
		temp = cnt;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> board[i][j];
		}
	}

	while (true)
	{
		if (check)
		{
			cout << hour - 1 << '\n' << temp;
			break;
		}
		memset(visited, false, sizeof(visited));
		Bfs();
	}

	return 0;
}

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

문제

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.

예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.

보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.

5 7
WLLWWWL
LLLWLLL
LWLWLWW
LWLWLLL
WLLWLWW

8

풀이

• BFS로 간단하게 풀리는 문제였다.
• 보물은 최단 거리에 있어 가장 긴 시간이 걸리는 위치에 존재하기 때문에 이동할 수 있는 육지(L)를 탐색하며 상하좌우를 탐색할 수 있을 때마다 1씩 증가시킨다. 2차원 배열에서 탐색하면서 증가된 가장 큰 수를 출력하면 된다.

코드

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

#define MAX 51
#define _X first
#define _Y second

char map[MAX][MAX];
int visited[MAX][MAX] = { 0, };

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

queue<pair<int, int>> q;

int r, c;
int dis = -1;

void Bfs(int x, int y)
{
	q.push({ x, y });
	visited[x][y] = 1;

	while (!q.empty())
	{
		pair<int, int> cur = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = cur._X + dx[i];
			int ny = cur._Y + dy[i];

			if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
			if (map[nx][ny] == 'W' || visited[nx][ny] != 0) continue;

			q.push({ nx, ny });
			visited[nx][ny] = visited[cur._X][cur._Y] + 1;
			if (dis < visited[nx][ny])
				dis = visited[nx][ny];
		}
	}


}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> r >> c;

	for (int i = 0; i < r; i++)
	{
		string str;
		cin >> str;
		for (int j = 0; j < c; j++)
		{
			map[i][j] = str[j];
		}
	}

	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			if (map[i][j] == 'L' && visited[i][j] == 0)
			{
				Bfs(i, j);
				memset(visited, 0, sizeof(visited));
			}
		}
	}

	cout << dis - 1;

	return 0;
}

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

5 17

4

#include <iostream>
#include <queue>

using namespace std;

#define MAX 1000001

int n, k;
int dis[MAX];
queue<int> q;

int Bfs(int start, int finish)
{
    q.push(n);
    while (!q.empty())
    {
        int cur = q.front();
        int dir[3] = { 1, -1, cur };    // 수빈이가 이동할 수 있는 방향 벡터
        q.pop();

        // 현재 위치가 동생의 위치라면 이동 횟수 반환
        if (cur == finish) return dis[cur];

        for (int i = 0; i < 3; i++)
        {
            int next = cur + dir[i];
            if (next < 0 || next >= MAX || dis[next] != 0) continue;
            q.push(next);
            dis[next] = dis[cur] + 1;
        }
    }
    return 0;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> k;

    int result = Bfs(n, k);
    cout << result;

    return 0;
}

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

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

5
28
0

풀이

• 기존 BFS/DFS에서 사용하는 방향 벡터를 나이트가 이동할 수 있는 8개의 좌표로 지정하여 BFS를 실행하였다.
• 테스트케이스가 여러개일 수 있으므로, 케이스를 입력할 때마다 큐와 2차원 배열을 비워주고 초기화해야 한다.

코드

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

#define MAX 301
#define _X first
#define _Y second

int board[MAX][MAX];
int dx[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int dy[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };

int t, l; // 테스트 케이스, 한 변의 길이
int posX, posY, tPosX, tPosY;
queue<pair<int, int>> q;

// 배열 초기화, 큐 비워주는 함수
void Reset(int side)
{       
    for (int i = 0; i < side; i++)
    {
        for (int j = 0; j < side; j++)
        {
            board[i][j] = 0;
        }
    }
    while (!q.empty()) q.pop();
}

int Bfs()
{
    while (!q.empty())
    {
        // 이동하려는 좌표가 시작 좌표면 안 움직여도 된다.
        if (posX == tPosX && posY == tPosY) return 0;

        // 현재 위치 x, y 저장
        pair<int, int> cur = q.front();
        int x = cur._X;
        int y = cur._Y;
        q.pop();

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

            // 범위 벗어나거나 이미 방문했으면 무시
            if (nx < 0 || nx >= l || ny < 0 || ny >= l) continue;
            if (board[nx][ny] != 0) continue;

            // 다음 위치가 이동하려던 위치면 이동 횟수 반환
            if (nx == tPosX && ny == tPosY) return board[x][y] + 1;
            
            q.push({ nx, ny });
            board[nx][ny] = board[x][y] + 1;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> t;

    while (true)
    {
        // 테스트 케이스 횟수만큼 다 입력하면 반복문 벗어나기
        if (t == 0) break;  
        cin >> l;
        Reset(l);

        cin >> posX >> posY >> tPosX >> tPosY;
        // 현재 위치 큐에 넣고 Bfs 실행 후 이동 횟수 출력
        q.push({ posX, posY });
        int result = Bfs();
        cout << result << '\n';
        t--;
    }

    return 0;
}

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

6 5
1 2
2 5
5 1
3 4
4 6

2

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

1

풀이

• 무방향 그래프(Undirected Graph)란 두 정점 사이에 방향이 없는 그래프를 뜻한다. 모든 정점이 연결되어 하나로 이루어질 수도 있고, 여러 개의 부분 그래프로 구성되어 있을 수도 있다.
• 연결 요소(Connected Component)란 무방향 그래프에서 나누어진 각각의 그래프를 뜻한다. 아래 그림의 경우, 2개의 연결 요소로 이루어져 있다고 볼 수 있다.

• 벡터를 이용한 인접리스트를 구현하여 문제를 해결하였다.
• 방문하지 않은 정점에 대해 Dfs를 실행하였고, 해당 정점과 이어진 모든 정점을 탐색할 수 있도록 Dfs를 사용하였다.
• 한 그래프에 대한 탐색이 종료되면 연결 요소의 개수(cnt)를 증가시킨다.

코드

#include <iostream>
#include <vector>

using namespace std;

#define MAX 1001

vector<int> vec[MAX];
bool visited[MAX];

int vertex, edge, from, to, cnt;

void Dfs(int v)
{
	visited[v] = true;

	for (int i = 0; i < vec[v].size(); i++)
	{
		int next = vec[v][i];
		if (!visited[next])
			Dfs(next);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> vertex >> edge;

	for (int i = 1; i <= edge; i++)
	{
		cin >> from >> to;
		vec[from].push_back(to);
		vec[to].push_back(from);
	}

	for (int i = 1; i <= vertex; i++)
	{
		if (!visited[i])
		{
			Dfs(i);
			cnt++;
		}
	}

	cout << cnt;

	return 0;
}