C++-এ Number of Connected Components: অ dirigir না করা গ্রাফে কানেক্টেড কম্পোনেন্ট গণনা

n সংখ্যক নোড (০ থেকে n-1 পর্যন্ত লেবেলড) এবং একটি অনির্দেশিত এজ লিস্ট দেওয়া আছে। গ্রাফে কতটি কানেক্টেড কম্পোনেন্ট (Connected Component) রয়েছে তা বের করতে হবে।

উদাহরণ

ইনপুট: n = 5, edges = [[0,1],[1,2],[3,4]]

আউটপুট: 2 (দুটি আলাদা কম্পোনেন্ট: {0,1,2} এবং {3,4})।

সমাধানের পদ্ধতি (DFS / Graph Traversal)

1. এজ লিস্ট থেকে অ্যাডজেসেন্সি লিস্ট graph তৈরি করুন।
2. ভিজিটেড অ্যারে visited[n] ইনিশিয়ালাইজ করুন।
3. ret = 0।
4. প্রতিটি নোড i = 0 থেকে n-1 এর জন্য:
   • যদি !visited[i] হয়, তবে dfs(i, graph, visited) কল করুন এবং ret++ করুন।
5. dfs(node, graph, visited):
   • যদি visited[node] হয়, তবে রিটার্ন।
   • visited[node] = true।
   • নোডের সব নেইবারের জন্য রিকারসিভলি dfs কল করুন।
6. ret রিটার্ন করুন।

C++ কোড উদাহরণ

#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;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{0,1},{1,2},{3,4}};
    cout << (ob.countComponents(5, v));
    return 0;
}

ইনপুট

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

আউটপুট

2