[그래프] BOJ 11724번 연결 요소의 개수

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

11724번: 연결 요소의 개수

- 문제 파악

정점의 개수와 간선의 개수가 주어지고 연결 요소의 개수를 출력하라

 

연결 요소 : 간선으로 이어진 정점들을 한 개의 연결 요소로 볼 수 있다. 간선으로 이어지지 않고 단독으로 있는 정점도 연결요소로 볼 수 있다.

 

- 정답

#include "bits/stdc++.h"

using namespace std;

int arr[1002][1002];
int check[1002];
int ans;

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


	int n, m;
	cin >> n >> m;

	stack<int> st;



	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		arr[a][b] = arr[b][a] = 1;
		check[a] = check[b] = 1;
	}

	for (int i = 1; i <= n; i++)
		check[i] = 1;

	for (int i = 1; i < 1002; i++)
	{
		if (check[i])
		{
			st.push(i);

			while (!st.empty())
			{
				int k = st.top();
				st.pop();

				check[k] = 0;

				for (int j = 0; j < 1002; j++)
				{
					if (arr[k][j] && check[j])
					{
						st.push(j);
					}
				}


			}

			ans++;

		}
	}

	cout << ans;

}