📃 coding test/◽ 백준
(백준/c++) 11724 - 연결 요소의 개수 / BFS, 그래프
핑크코냥
2024. 8. 16. 16:17
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