연결 요소의 개수(11724)

연결 요소의 개수(11724)

풀이

모든 시작점에서 DFS방식을 이용해 탐색하게 설계하고 방문한 노드는 다시 방문하지 않도록 제한함으로서

몇 개의 연결 요소의 개수가 있는지 판별한다.

코드

#pragma warning(disable: 4996) #include #include #include using namespace std; queue q; bool visited[1001] = {false}; vector v[1001]; void DFS(int n) { //printf("%d ", n); visited[n] = true; for (int i = 0; i < v[n].size(); i++) { if (visited[v[n].at(i)] == false) { DFS(v[n].at(i)); } } } int main() { int N, M, a, b; scanf("%d %d", &N;,&M;); for (int i = 1; i <= M; i++) { scanf("%d %d", &a;, &b;); v[a].push_back(b); v[b].push_back(a); } int count = 0; for (int j = 1; j <= N; j++) { if (visited[j] == false){ DFS(j); count++; } } printf("%d", count); return 0; }

from http://sy4406.tistory.com/17 by ccl(A) rewrite - 2021-08-15 18:26:22