মডিউল ১_৩ঃ অ্যাডজাসেন্সি ম্যাট্রিক্স ইমপ্লিমেন্টশন

অ্যাডজাসেন্সি ম্যাট্রিক্স ইমপ্লিমেন্টশন

গ্রাফের Number of nodes (n) and Number of Edges (e) ইনপুট নেয়া হল। একটি NxN সাইজের 2D অ্যারে delcare করা হল।

int n, e;
cin >> n >> e;
int mat[n][n];

memset build-in function ব্যবহার করে 2D অ্যারের সকল ইনডেক্সে 0 assign করে দেয়া হল।

memset(mat, 0, sizeof(mat));

e বার লুপ চালিয়ে, লুপের ভিতর edge এর নোড ২টি a and b ইনপুট নেয়া হল । এরপর 2D অ্যারের mat[a][b] ইনডেক্স ও mat[b][a] ইনডেক্সে 1 assign করে দেয়া হল। এতে করে বুঝা যাবে a নোডের সাথে b নোডের edge আছে এবং b নোডের সাথে a নোডের edge আছে।

while (e--)
{
    int a, b;
    cin >> a >> b;
    mat[a][b] = 1;
    mat[b][a] = 1;
}

এরপর manually চেক করলাম ইনপুট নেয়া গ্রাফে 3 নোডের সাথে 1 নোডের কোন edge আছে কিনা। সেইটি আমরা বুঝতে পারব যদি mat[3][1] ইনডেক্সের মানটি 1 হয়।

if (mat[3][1] == 1)
    cout << "connection ache";
else
    cout << "connection nai";

---

সম্পূর্ণ কোড অ্যাডজাসেন্সি ম্যাট্রিক্স ইমপ্লিমেন্টশন

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, e;
    cin >> n >> e;
    int mat[n][n];
    memset(mat, 0, sizeof(mat));
    while (e--)
    {
        int a, b;
        cin >> a >> b;
        mat[a][b] = 1;
        mat[b][a] = 1;
    }
    if (mat[3][1] == 1)
        cout << "connection ache";
    else
        cout << "connection nai";
    return 0;
}