반응형
문제
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.
출력
첫째 줄에 연결 요소의 개수를 출력한다.
예제 입력 1
6 5
1 2
2 5
5 1
3 4
4 6
예제 출력 1
2
예제 입력 2
6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3
예제 출력 2
1
/*[11724] baekjoon 연결 요소의 개수*/
#include <bits/stdc++.h>
using namespace std;
#define MAXN ((int) 1e3)
int N,M,cnt=0;
int s[MAXN*MAXN], e[MAXN*MAXN];
int mat[MAXN+10][MAXN+10];
int visited[MAXN+10];
void InputData(){
int u, v;
cin >> N >> M;
for (int i=0; i<M; i++){
cin >> u >> v;
mat[u][v] = 1;
mat[v][u] = 1;
}
}
void DFS(int x){
visited[x] = 1;
for(int i =1; i<=N; i++){
if(mat[x][i] ==1 && visited[i] ==0){
DFS(i);
}
}
}
void BFS(int x){
int t;
queue <int> q;
q.push(x);
visited[x] = 1;
while( !q.empty()){
t = q.front();
q.pop();
for(int i=1; i<=N; i++){
if(mat[t][i] == 1 && visited[i] ==0){
q.push(i);
visited[i] =1;
}
}
}
}
void Solve(){
for(int i=1; i<=N; i++){
if(visited[i] ==0){
BFS(i);
cnt++;
}
}
cout << cnt << endl;
}
int main(){
InputData();
Solve();
return 0;
}
/*[11724] baekjoon 연결 요소의 개수*/
반응형
'Algorithm > BFS,DFS' 카테고리의 다른 글
[c++][algoritm][baekjoon]7562 나이트의 이동 (0) | 2021.09.23 |
---|---|
[c++][algorithm][baekjoon][7569]토마토 (0) | 2021.08.29 |
[c++][baekjoon][2468]안전 영역 (0) | 2021.08.24 |
[c++][baekjoon][4963]섬의 개수 (0) | 2021.08.24 |
[c++]백준 2206 벽 부수고 이동하기 (0) | 2021.04.26 |