C++ এ একটি অনির্দেশিত গ্রাফে সংযুক্ত উপাদানের সংখ্যা

ধরুন আমাদের n নোড রয়েছে এবং সেগুলিকে 0 থেকে n - 1 পর্যন্ত লেবেল করা হয়েছে এবং অনির্দেশিত প্রান্তগুলির একটি তালিকাও দেওয়া হয়েছে, একটি অনির্দেশিত গ্রাফে সংযুক্ত উপাদানগুলির সংখ্যা খুঁজে পেতে আমাদের একটি ফাংশন সংজ্ঞায়িত করতে হবে৷

সুতরাং, যদি ইনপুট হয় n =5 এবং প্রান্ত =[[0, 1], [1, 2], [3, 4]],

তাহলে আউটপুট হবে 2

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন, এটি নোড, গ্রাফ, ভিজিটেড নামে একটি অ্যারে নেবে,

• যদি পরিদর্শন করা [নোড] মিথ্যা হয়, তাহলে -

  • পরিদর্শন [নোড] :=সত্য

• আরম্ভ করার জন্য i :=0, যখন i <গ্রাফের আকার [নোড], আপডেট করুন (i 1 দ্বারা বৃদ্ধি করুন), করুন −

  • dfs(গ্রাফ[নোড, i], গ্রাফ, পরিদর্শন করা হয়েছে)

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• n

  আকারের পরিদর্শন করা একটি অ্যারে সংজ্ঞায়িত করুন

• যদি n অ-শূন্য হয়, তাহলে −

  • একটি অ্যারে গ্রাফ সংজ্ঞায়িত করুন[n]

• আরম্ভ করার জন্য i :=0, যখন i <প্রান্তের আকার, আপডেট (i 1 দ্বারা বৃদ্ধি), −

  • u :=প্রান্ত[i, 0]

  • v :=প্রান্ত[i, 1]

  • গ্রাফ[u]

    -এর শেষে v সন্নিবেশ করান

  • গ্রাফের শেষে u ঢোকান[v]

• ret :=0

• আরম্ভ করার জন্য i :=0, যখন i

  • যদি পরিদর্শন না করা হয় [i] অ-শূন্য, তাহলে −

    • dfs(i, গ্রাফ, পরিদর্শন করা)

    • (রেট 1 দ্বারা বৃদ্ধি করুন)

• রিটার্ন রিটার্ন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   void dfs(int node, vector<int< graph[], vector<bool>& visited){
      if(visited[node]) return;
         visited[node] = true;
      for(int i = 0; i < graph[node].size(); i++){
         dfs(graph[node][i], graph, visited);
      }
   }
   int countComponents(int n, vector<vector<int<>& edges) {
      vector <bool> visited(n);
      if(!n) return 0;
         vector <int< graph[n];
      for(int i = 0; i < edges.size(); i++){
         int u = edges[i][0];
         int v = edges[i][1];
         graph[u].push_back(v);
         graph[v].push_back(u);
      }
      int ret = 0;
      for(int i = 0; i < n; i++){
         if(!visited[i]){
            dfs(i, graph, visited);
            ret++;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int<> v = {{0,1},{1,2},{3,4}};
   cout << (ob.countComponents(5, v));
}

ইনপুট

5, [[0,1],[1,2],[3,4]]

আউটপুট

2