[BaekJoon] 백준 11724번 연결 요소의 개수

 

[BaekJoon] 백준 11724번 연결 요소의 개수

 

 

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

 

 

내코드

 

- dfs를 이용해서 푸는 기본적인 그래프 문제

- 정점들을 차례대로 방문하면서 인접한 정점을 스택에 넣어준다. 이때 이미 방문했던 정점이면 패스. 패스하지 않은 정점의 개수가 연결요소의 개수. 이미 방문했던 정점이라는 것은 이전의 정점에서 dfs를 돌렸을때 연결되있어서 방문했다는 의미이니까.

- 아래는 아이패드에 정리한 내용

 

백준 11724번 연결 요소의 개수.pdf

2.62MB

 

 

코드블럭

#include <iostream>
#include <string>
#include <vector>
#include <stack>

using namespace std;

int n, m;
vector<int> arr[1001];
bool visited[1001] = { false, };

int dfs() {
	stack<int> st;
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (visited[i]) continue;
		st.push(i);
		cnt++;
		visited[i] = true;
		while (!st.empty()) {
			int cur = st.top();
			st.pop();
			for (int j = 0; j < arr[cur].size(); j++) {
				int nxt = arr[cur][j];
				if (visited[nxt]) continue;
				st.push(nxt);
				visited[nxt] = true;
			}
		}
	}
	return cnt;
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		arr[a].push_back(b);
		arr[b].push_back(a);
	}
	cout << dfs();
	return 0;
}

 

참고

https://blog.encrypted.gg/908?category=773649