https://www.acmicpc.net/problem/11724
해당 문제는 그래프의 개념과 BFS를 동시에 물어보는 가장 기초적이고 핵심적인 문제이며 코드 구성을 외우고 이해할 필요가 있는 문제이다. 코드는 아래와 같다.
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> adj[1005];
bool vis[1005];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int num = 0;
for (int i = 1; i <= n; i++)
{
if (vis[i]) continue;
num++;
queue<int> q;
q.push(i);
vis[i] = true;
while (!q.empty())
{
int cur = q.front();
q.pop();
for (auto nxt : adj[cur])
{
if (vis[nxt] == true) continue;
q.push(nxt);
vis[nxt] = true;
}
}
}
cout << num;
}
'CS(Computer Science)지식 > [C++][코딩 테스트] 자료구조 및 알고리즘' 카테고리의 다른 글
백준 5667번: 결혼식 (C++) (0) | 2024.02.02 |
---|---|
백준 1260번: DFS와 BFS (C++) (0) | 2024.02.02 |
백준 2075번: N번째 큰 수 (C++) (0) | 2024.02.02 |
백준 1927번: 최소 힙 (C++) (0) | 2024.02.02 |
백준 1715번: 카드 정렬하기 (C++) (3) | 2024.01.31 |