[백준] 11724번 연결 요소의 개수 - C++ (DFS, 그래프)
2022. 11. 10. 18:03
solving/C, C++
풀이에 https://velog.io/@polynomeer/%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8CConnected-Component 포스팅을 참고하였음을 밝힙니다. 발상 1. 그래프 + 주어진 그래프의 정점들을 DFS를 이용해 탐색하여 연결 요소의 개수를 밝히는 문제이다. 2. 그래프는 우선 C언어에 내장된 vector를 이용해 구현하고, 방향이 없는 그래프이므로 하나를 입력받을 때마다 v->u, u->v 두 가지 모두를 입력한다, 3. DFS를 이용하면 한 개의 연결 요소 그래프에 속한 노드를 전부 탐색할 수 있으므로, false값을 가진 node에 대해 DFS를 수행해 해당 연결 요소의 노드를 전부 탐색하고 답에 +=1을 해준다. 그리고 또 false값을 가진 node가 ..