[백준/C++] 11724번_연결 요소의 개수
문제는 다음과 같습니다.
연결 요소의 개수를 구하는 방법은 다음과 같습니다.
한 정점으로부터 dfs를 수행하였을 때 연결된 그래프가 한 개의 연결요소가 됩니다.
그리고 위의 그래프에서 포함된 정점을 제외시키고, 남은 점들에서 다시 dfs를 수행하면 됩니다.
정점이 고립?되어 있어도 이는 하나의 연결요소가 됩니다.
저는 연결요소의 개수를 변수 res로 계산하였고,
모든 정점에 대해서 dfs를 수행하였습니다.
❗️단, dfs를 수행하기 위해서는 시작 정점이 'ch[정점]==0' 이어야 합니다.❗️ (➡️이미 다른 그래프의 연결요소에 포함되어있지 않아야 합니다.)
전체 코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
int n, m, res=0;
vector<int> v[1001];
int ch[1001]={0, };
void DFS(int k){
for(int i=0; i<v[k].size(); i++){
if(ch[v[k][i]]==0){
ch[v[k][i]]=1;
DFS(v[k][i]);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i=0; i<m; i++){
int a, b; cin>>a>>b;
v[a].emplace_back(b); v[b].emplace_back(a);
}
ch[1]=0; DFS(1); res+=1;
for(int i=2; i<=n; i++){
if(ch[i]==0){
ch[i]=1;
DFS(i);
res++;
}
}
cout<<res<<"\n";
return 0;
}
2/16 수요일 복습)
#include <bits/stdc++.h>
using namespace std;
vector<int> v[1001];
int ch[1001]={0, };
int n, m;
void DFS(int k){
for(int i=0; i<v[k].size(); i++){
if(ch[v[k][i]]==0){
ch[v[k][i]]=1;
DFS(v[k][i]);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i=0; i<m; i++){
int t1, t2; cin>>t1>>t2;
v[t1].emplace_back(t2); v[t2].emplace_back(t1);
}
int res=0;
// DFS수행
for(int i=1; i<=n; i++){
if(ch[i]==0){
ch[i]=1;
DFS(i);
res++;
}
}
cout<<res<<endl;
return 0;
}
Author And Source
이 문제에 관하여([백준/C++] 11724번_연결 요소의 개수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ssssujini99/백준C-11724번연결-요소의-개수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)