반응형
문제 링크
코드
#include <bits/stdc++.h>
using namespace std;
vector<int> p[1001];
bool vis[1001];
int n, m, a, b, ans = 0;
void bfs(int x) {
queue<int> Q;
Q.push(x);
vis[x] = 1;
while (!Q.empty()) {
x = Q.front();
Q.pop();
for (int i = 0; i < p[x].size(); i++) {
int y = p[x][i];
if (!vis[y]) {
Q.push(y);
vis[y] = 1;
}
}
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
while (m--) {
cin >> a >> b;
p[a].push_back(b);
p[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
if (vis[i]) continue;
ans++;
bfs(i);
}
cout << ans;
}
설명
연결 요소 (Connected Component)를 BFS (너비 우선 탐색)하는 방법이다.
(주의) 기록용으로 작성한 글입니다. 좋은 코드가 아닐 수 있습니다.
댓글 환영합니다!
반응형
'Algorithm > BOJ' 카테고리의 다른 글
[백준/BOJ] 14487번 - 욱제는 효도쟁이야!! (C++) (0) | 2022.03.25 |
---|---|
[백준/BOJ] 11866번 - 요세푸스 문제 0 (C++) (0) | 2022.03.25 |
[백준/BOJ] 11721번 - 열개씩 끊어 출력하기 (C++) (0) | 2022.03.25 |
[백준/BOJ] 11650번 - 좌표 정렬하기 (C++) (0) | 2022.03.25 |
[백준/BOJ] 11653번 - 소인수분해 (C++) (0) | 2022.03.25 |
댓글