문제
접근 방법
dfs로 접근해 거의 리니어한 타임에 문제를 풀수 있다. 그 대신 사이클이 있는 경우를 대비해 방문한 노드를 체크하고 방문했을 경우에는 다시 해당 노드로 접근하지 않는다.
코드
#include <iostream> #include <cstring> using namespace std; int N, M; int map[1001][1001]; int visited[1001]; int cnt; int dfs(int node) { visited[node] = 1; for(int i = 1; i <= N; i++) { if(map[node][i] && !visited[i]) { dfs(i); } } return 0; } int main() { cin >> N >> M; memset(map, 0, sizeof(map)); memset(visited, 0, sizeof(visited)); int r, c; for(int i = 0; i < M; i ++) { cin >> r >> c; map[r][c] = map[c][r] = 1; } for(int i = 1; i <= N; i ++) { if(!visited[i]){ dfs(i); cnt++; } } cout << cnt; return 0; }