백준 11724번:연결 요소의 개수

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

11724번: 연결 요소의 개수

여기서 연결 요소는 아래와 같이 나누어지는 각각의 그래프를 연결요소라 한다.

1.연결요소에 속한 모든 정점은 연결되어 있어야한다.

2.다른 연결요소에 속한 정점과 연결하는 경로가 있으면 안된다.

이 그래프는 연결요소가 2개다

즉 이 문제는 그래프 탐색을 이용해서 연결요소개수를 세면 된다.

나는 DFS를 이용해서 구했고 DFS를 할때마다 방문한 정점을 check배열에 방문했다고 표시했는데 

이 표시값 차이를 이용해서 연결요소 개수를 구했다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<stack>
#include<queue>
#define PI 3.1415926535
using namespace std;
bool check1[1001] = { 0 };
vector<int> d[1002];
int cnt = 0;
void dfs(int a) {
	check1[a] = true;
	for (int i = 0; i < d[a].size(); i++) {
		int next = d[a][i];
		if (check1[next] == false)
			dfs(next);
	}
}
int main()
{	
	int n=0, m=0,v=0;
	cin >> n >> m;
	while (m--) {
		int a, b;
		cin >> a >> b;
		d[a].push_back(b);
		d[b].push_back(a);
	}
	for (int i = 1; i <= n; i++){
		sort(d[i].begin(), d[i].end());}
	int check = 0;
	for (int i = 1; i <= n; i++) {         //연결요소를 구하기위해 모든정점 DFS구현
		dfs(i);
		int ans = check;                   //ans는 전에 탐색한 DFS가 발견한 정점의 수
		check = 0;
		for (int i = 1; i <= n; i++) {      //check는 이번에 탐색한 DFS가 발견한 정점의수
			if (check1[i] == true) {
				check++;   
			}
		}
		if (ans != check)                //check와 ans가 다르면 그래프가 다른 것이므로 연결요소 증가
			cnt++;
	}
	cout << cnt;
	return 0;
}