연결 요소의 개수 11724

연결 요소의 개수 11724

연결 요소의 개수 11724

풀이코드 ( BFS )

#include #include #include #include using namespace std; // 11724 연결 요소의 개수 int n, m; vector adjList[1001]; queue q; bool isVisited[1001]; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> m; for(int i = 0; i < m; i++){ int from, to; cin >> from >> to; adjList[from].push_back(to); adjList[to].push_back(from); } // input 이 어떤 순서로 들어올지 알 수 없기에 오름차순으로 인접 리스트를 정렬해준다. for(int i = 1; i <= n; i++){ sort(adjList[i].begin(), adjList[i].end()); } fill_n(isVisited, 1001, false); // bfs int count = 0; // 모든 node 로 출발점을 설정한다. for(int start = 1; start <= n; start++){ // 방문했다면 생략 if(isVisited[start]) continue; // 방문하지 않은, start 부터 bfs 시작 q.push(start); isVisited[start] = true; while(!q.empty()){ int currentNode = q.front(); q.pop(); for(int i = 0; i < adjList[currentNode].size(); i++){ int nextNode = adjList[currentNode][i]; // 다음 노드를 방문했었다면 생략 if(isVisited[nextNode]) continue; // 다음 노드를 방문하지 않았다면 q.push(nextNode); isVisited[nextNode] = true; } } count++; } cout << count << '

'; }

해설

적용한 레시피 / 방법론 + 접근법

1

풀이

1

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

1

from http://private-k.tistory.com/134 by ccl(A) rewrite - 2021-10-02 17:00:39