[BOJ/C+]#11724接続要素の数
🍎 質問リンク
接続リストとして入力します. boolアクセス配列 ノード順にナビゲートし、まだアクセスしていない場合はbfsまたはdfsを呼び出し、cnt++
問題を解く
BFSDFSの2つの方法で解決できます.入力、main
int main(){
cin>>N>>M;
for(int i=0;i<M;i++){
int s,e;
cin>>s>>e;
map[s].push_back(e);
map[e].push_back(s);
}
int cnt=0;
for(int i=1;i<=N;i++){
if(!visited[i]){
bfs(i);
//dfs(i);
cnt++;
}
}
cout<<cnt<<"\n";
}BFS
void bfs(int start){
queue<int> q;
visited[start]=true;
q.push(start);
while(!q.empty()){
int cur=q.front();
q.pop();
for(int i=0;i<map[cur].size();i++){
if(!visited[map[cur][i]]){
visited[map[cur][i]]=true;
q.push(map[cur][i]);
}
}
}
}DFS
void dfs(int start){
visited[start]=true;
for(int i=0;i<map[start].size();i++){
if(!visited[map[start][i]]){
visited[map[start][i]]=true;
dfs(map[start][i]);
}
}
}
完全なコード
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define MAX 1000+1
vector<int> map[MAX];
bool visited[MAX];
int N,M;
void bfs(int start){
queue<int> q;
visited[start]=true;
q.push(start);
while(!q.empty()){
int cur=q.front();
q.pop();
for(int i=0;i<map[cur].size();i++){
if(!visited[map[cur][i]]){
visited[map[cur][i]]=true;
q.push(map[cur][i]);
}
}
}
}
void dfs(int start){
visited[start]=true;
for(int i=0;i<map[start].size();i++){
if(!visited[map[start][i]]){
visited[map[start][i]]=true;
dfs(map[start][i]);
}
}
}
int main(){
cin>>N>>M;
for(int i=0;i<M;i++){
int s,e;
cin>>s>>e;
map[s].push_back(e);
map[e].push_back(s);
}
int cnt=0;
for(int i=1;i<=N;i++){
if(!visited[i]){
bfs(i);
//dfs(i);
cnt++;
}
}
cout<<cnt<<"\n";
}
Reference
この問題について([BOJ/C+]#11724接続要素の数), 我々は、より多くの情報をここで見つけました https://velog.io/@inryu/BOJ-C-11724-연결요소의-개수テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol