[C++]백준 - 11724번 문제

11724번: 연결 요소의 개수 (acmicpc.net)

11724번: 연결 요소의 개수

 

111724번 : 연결 요소의 개수

---

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

 

 

출력

---

첫째 줄에 연결 요소의 개수를 출력한다.

 

 

 

---

 

생각해 볼 점

---

탐색 문제이므로, DFS 혹은 BFS 알고리즘을 써서

 

몇 개의 연결 요소가 있는지 체크만 하면 될 것 같습니다.

 

코드

---

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main()
{
	int N, M;
	scanf("%d %d", &N, &M);

	vector<int>* edges = new vector<int>[N];
	bool* visited = new bool[N];
	fill_n(visited, N, false);

	for (int i = 0; i < M; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		a--; b--;

		edges[a].push_back(b);
		edges[b].push_back(a);
	}

	stack<int> st;
	int ans = 0;
	for (int i = 0; i < N; i++)
	{
		if (visited[i]) continue;
		ans++;
		
		//DFS 탐색
		st.push(i);
		visited[i] = true;
		while (!st.empty())
		{
			int current = st.top();
			st.pop();

			for (int next : edges[current])
			{
				if (visited[next]) continue;

				visited[next] = true;
				st.push(next);
			}
		}
	}

	printf("%d", ans);

	delete[] visited;
	delete[] edges;
	return 0;
}

 

그 외

---