C++-এ অনির্দেশিত গ্রাফে এজ (Edge) সংখ্যা গণনা

একটি অনির্দেশিত গ্রাফে (undirected graph) মোট কতগুলো এজ (edge) আছে তা বের করতে হবে। অনির্দেশিত গ্রাফ হলো কিছু ভার্টেক্স (vertex) যেগুলো সংযুক্ত হয়ে একটি গ্রাফ তৈরি করে, যেখানে সকল এজ দ্বিমুখী (bidirectional)।

দৃশ্যাবলীকরণ

ইনপুট উদাহরণ

insert(graph_list, 0, 1);
insert(graph_list, 0, 2);
insert(graph_list, 1, 2);
insert(graph_list, 1, 4);
insert(graph_list, 2, 4);
insert(graph_list, 2, 3);
insert(graph_list, 3, 4);

আউটপুট

count of edges are: 7

সমাধানের পদ্ধতি

1. এডজেসেন্সি লিস্ট (adjacency list) ব্যবহার করে গ্রাফ সংরক্ষণ করুন।
2. count_edges ফাংশনে count = 0 ইনিশিয়ালাইজ করুন।
3. সব ভার্টেক্সের জন্য লুপ চালিয়ে count += graph_list[i].size() করুন।
4. অনির্দেশিত গ্রাফে প্রতিটি এজ দুবার গণনা হয় (উভয় ভার্টেক্স থেকে), তাই ফাইনাল কাউন্ট ২ দিয়ে ভাগ করুন।

প্রোগ্রাম উদাহরণ

#include <bits/stdc++.h>
using namespace std;

void insert(list<int> graph_list[], int u, int v) {
    graph_list[u].push_back(v);
    graph_list[v].push_back(u);
}

void count_edges(list<int> graph_list[], int v) {
    int count = 0;
    for (int i = 0; i < v; i++) {
        count += graph_list[i].size();
    }
    count = count / 2;
    cout << "count of edges are: " << count;
}

int main() {
    int vertices = 5;
    list<int> graph_list[vertices];
    
    insert(graph_list, 0, 1);
    insert(graph_list, 0, 2);
    insert(graph_list, 1, 2);
    insert(graph_list, 1, 4);
    insert(graph_list, 2, 4);
    insert(graph_list, 2, 3);
    insert(graph_list, 3, 4);
    
    count_edges(graph_list, vertices);
    return 0;
}

আউটপুট

count of edges are: 7