C++で森の木の数を数える

与えられた森の頂点（木のコレクション）。目標は、その森の木の数を見つけることです。これを行うには、フォレストでDFS（深さ優先探索）アルゴリズムを実行します。

例

入力

edges = { { 1,3 }, {2,8}, {2,6}, {3,5}, {3,7}, {4,8} }

出力

Count of number of trees in a forest are: 3

説明

森に存在する木の数は-

以下のプログラムで使用されるアプローチは次のとおりです −

このアプローチでは、グラフに深さ優先探索アルゴリズムを再帰的に適用します。接続されているすべてのノードが1つのソースから訪問済みとしてマークされている場合（つまり、ツリーが形成されている場合）、カウントをインクリメントします。

• 整数の頂点をグラフ上の頂点の数として取ります。

• 頂点を整数として格納するためのベクトルvectorvec[vertice]を取ります。

• 関数insert（vector vec []、int parent、int child）はvec []を受け取り、そのベクトルのノードの親と子の間にエッジを追加します。

• vec [parent] .push_back（child）およびvec [child] .push_back（parent）を使用してエッジを追加します。

• 関数recurred（int temp、vector vec []、vector ＆check）は、開始頂点温度からグラフにDFSを適用します。

• 配列check[temp]は、true/falseを使用してノードを訪問済み/未訪問として設定するために使用されます。

• forループを使用してベクトルvec[]をトラバースし、check [vec [temp] [i]]がfalseの場合、接続されたノードに対して再帰的にcallrecurred（vec [temp] [i]、vec、check）します。

• 関数Trees_Forest（vector vec []、int vertice）はvec []を受け取り、vec[]の隣接リストとして指定されたフォレスト内のツリーの数を返します。

• 森林の初期カウントを0とします。

• vector check（vertice、false）を使用して、グラフの頂点を訪問済みとしてマークします。

• forループを使用してすべての頂点をトラバースします。

• check [i]がfalseの場合、recurred（i、vec、check）とincrementcountを使用してdfsを適用します。

• すべてのループの最後に、結果としてカウントが返されます。

例

#include<bits/stdc++.h>
using namespace std;
void insert(vector<int> vec[], int parent, int child){
   vec[parent].push_back(child);
   vec[child].push_back(parent);
}
void recurred(int temp, vector<int> vec[], vector<bool> &check){
   check[temp] = true;
   int size = vec[temp].size();
   for(int i = 0; i < size; i++){
      if (check[vec[temp][i]] == false){
         recurred(vec[temp][i], vec, check);
      }
   }
}
int Trees_Forest(vector<int> vec[], int vertice){
   int count = 0;
   vector<bool> check(vertice, false);
   for(int i = 0; i < vertice; i++){
      if(check[i] == false){
         recurred(i, vec, check);
         count++;
      }
   }
   return count;
}
int main(){
   int vertice = 9;
   vector<int> vec[vertice];
   insert(vec, 1, 3);
   insert(vec, 2, 8);
   insert(vec, 2, 6);
   insert(vec, 3, 5);
   insert(vec, 3, 7);
   insert(vec, 4, 8);
   cout<<"Count of number of trees in a forest are: "<<Trees_Forest(vec, vertice);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of number of trees in a forest are: 3