(백준/c++) 11724 - 연결 요소의 개수 / BFS, 그래프📃 coding test/◽ 백준2024. 8. 16. 16:17
Table of Contents
728x90
"(백준/c++) 11724 - 연결 요소의 개수 / BFS, 그래프"
https://www.acmicpc.net/problem/11724
🏆 solved.ac 난이도: 실버2
난이도는 쉬웠다. DFS, BFS 아무거나 골라서 풀수 있는 문제이다.
하지만~ 나는 5번 정도 틀렸다.
이유는 방향성이 없는 그래프인데 방향성이 있게 한 쪽만 입력해주고 있었다. ㅠㅠ
방향성이 없는 그래프라면 꼭 정점 양쪽을 비교할 수 있도록 해주자.

// 연결 요소의 개수
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
bool visit[1001] = { false, };
vector<int> distributingLine[1001];
queue<int> que;
int main(void)
{
int N, M;
cin >> N >> M;
for (int i = 0; i < M; ++i)
{
int u, v;
cin >> u >> v;
distributingLine[u].push_back(v);
distributingLine[v].push_back(u);
}
int count = 0;
for (int i = 1; i <= N; ++i)
{
if (visit[i])
{
continue;
}
que.push(i);
visit[i] = true;
//bool check = false;
count++;
while (!que.empty())
{
int temp = que.front();
//visit[temp] = true;
que.pop();
for (int j = 0; j < distributingLine[temp].size(); ++j)
{
if (visit[distributingLine[temp][j]] == false)
{
visit[distributingLine[temp][j]] = true;
que.push(distributingLine[temp][j]);
//check = true;
}
}
}
//if (check)
//{
//}
}
cout << count;
return 0;
}

728x90
'📃 coding test > ◽ 백준' 카테고리의 다른 글
(백준/c++) 10026 - 적록색약 / BFS, 그래프 (0) | 2024.08.20 |
---|---|
(백준/c++) 11403 - 경로찾기 / BFS, 그래프 (0) | 2024.08.16 |
(백준/c++) 14940 - 쉬운 최단 거리 / DFS, 그래프 (0) | 2024.08.16 |
(백준/ C++) 12101- 1, 2, 3 더하기2 / 다이나믹 프로그래밍, 재귀 (0) | 2024.07.19 |
(백준/ C++) 1010 - 다리 놓기 / 다이나믹 프로그래밍, 재귀 (0) | 2024.07.19 |
@핑크코냥 :: 핑크코냥
안 하는 것 보다 낫겠지
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!