মডিউল ১৩_৩ঃ এডজেসেন্সি লিস্ট টু এডজেসেন্সি ম্যাট্রিক্স পার্ট-১

আমরা এখন দেখবো কিভাবে একটি গ্রাফ এর এডজেসেন্সি লিস্ট দেওয়া থাকলে সেটাকে আমরা এডজেসেন্সি ম্যাট্রিক্সে রুপান্তর করতে পারি।

এইটি বুঝার জন্য আমরা একটি গ্রাফ নেই।

এই গ্রাফ এর এডজেসেন্সি লিস্টটি হবেঃ

আমরা একটি ম্যাট্রিক্স রাখবো যার সারি এবং কলাম সংখ্যা উভয়ই হবে নোড সংখ্যার সমান। আর শুরুতে সকল এলিমেন্টে ০ রাখবো। আর শুধু যে এলিমেন্ট গুলোর সারি এবং কলাম সংখ্যা সমান তাদের ১ রাখবো। কারন তারা সেলফ নোড।

// Some code
    int mat[n][n];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            mat[i][j] = 0;
            if (i == j)
                mat[i][j] = 1;
        }
    }

এডজেসেন্সি ম্যাট্রিক্স এর ক্ষেত্রে সারি সংখ্যা বলতে বোঝায় সোর্স আর কলাম সংখ্যা বলতে বোঝার ডেস্টিনেশন। অর্থাৎ ম্যাট্রিক্সের ১,২ ইন্ডেক্সে ১ আছে মানে বোঝায় ১ থেকে ২ এ একটি এজ আছে।

এবার আমরা প্রত্যেকটি নোড এর এডজেসেন্সি লিস্ট এ যাবো আর সেই লিস্ট এর প্রত্যেকটি ভ্যালু এর জন্য ম্যাট্রিক্স এর সেই নোড ও সেই নোড এর লিস্ট এর কারেন্ট ভ্যালু তম এলিমেনট এর ভ্যালু ১ করে দিব।

তাহলে উপরের গ্রাফ এর জন্য ম্যাট্রিক্সটি হবেঃ

// Some code
    for (int i = 0; i < n; i++)
    {
        for (int child : adj[i])
        {
            mat[i][child] = 1;
        }
    }    

সম্পূর্ণ কোডঃ

// Some code
#include <bits/stdc++.h>
using namespace std;
void convert(int n, vector<int> adj[])
{
    int mat[n][n];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            mat[i][j] = 0;
            if (i == j)
                mat[i][j] = 1;
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int child : adj[i])
        {
            mat[i][child] = 1;
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << mat[i][j] << " ";
        }
        cout << endl;
    }
}
int main()
{
    int n, e;
    cin >> n >> e;
    vector<int> v[n];
    while (e--)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    convert(n, v);
    return 0;
}