(백준/c++) 11724 - 연결 요소의 개수 / BFS, 그래프

"(백준/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; 
}