728x90
문제
https://www.acmicpc.net/problem/11724
11724번: 연결 요소의 개수
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주
www.acmicpc.net
문제 해결
1. 인접 리스트로 정점들을 저장한다.
2. 1~N까지 방문하지 않은 노드들을 DFS 한다.
3. 방문할 때 마다 cnt를 해준다.
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | #include <iostream> #include <vector> #define Max 1001 using namespace std; int N,M,cnt = 0; vector <int> adj[Max]; bool visit[Max] = {false}; bool visited[Max] = {false}; void DFS(int node){ visit[node] = true; visited[node] = true; for(int i = 0;i<adj[node].size();i++){ int next_node = adj[node][i]; if(visit[next_node]){continue;} else{DFS(next_node);} } } int main(void){ cin >> N >> M; for(int i = 0;i<M;i++){ int a,b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } for(int i = 1;i<=N;i++){ if(visited[i]){continue;} else{ visited[i] = true; DFS(i); cnt++; } } cout << cnt; } | cs |
728x90
'그래프 이론 > BFS, DFS 알고리즘' 카테고리의 다른 글
[C++][DFS(깊이 우선탐색) 알고리즘] (0) | 2020.12.04 |
---|---|
[백준/C++][나이트의 이동(7562번)] (0) | 2020.12.02 |
[백준/C++][인구이동(16234번)] (0) | 2020.11.28 |
[백준/C++][(1167번)트리의 지름] (0) | 2020.11.21 |
[백준/C++] 치즈(2638번) (0) | 2020.11.11 |