[テストコード]bj 11724接続要素の個数-C++
[質問]
方向のないグラフィックが得られる場合は、接続要素の数を計算するプログラムを作成します.
[入力]
第1行は、頂点の個数Nと、幹線の個数Mとを与える.(1<=N<=10000, 1
[出力]
接続要素の数を最初の行に出力します.
[アクセス]
方向図の問題はありません.
グラフィックを実装する方法は、大きく2 D配列と接続リストに分けられます.
図面の接続要素(connected components)は、次の条件を満たす必要があります.
1.エレメント内のすべての頂点を接続するパスが必要です.
2.他の接続要素に属する頂点に接続するパスは使用できません.
このような接続要素を求めるにはbfs,dfsを用いる必要がある
[コード]
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
vector<int> graph [1001];
bool visited[1001];
void dfs(int v) {
visited[v] = true;
for (int i = 0; i < graph[v].size(); i++) {
int next = graph[v][i];
if (visited[next] == false)
dfs(next);
}
}
int main() {
int N, M; //정점, 간선
int count=0;
cin >> N >> M;
for (int i = 0; i < M; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
for (int i = 1; i < N; i++) {
if (visited[i] == false) {
dfs(i);
count++;
}
}
cout << count;
return 0;
}Reference
この問題について([テストコード]bj 11724接続要素の個数-C++), 我々は、より多くの情報をここで見つけました https://velog.io/@secdoc/코딩테스트bj11724-연결-요소의-개수-Cテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol