কনসেপ্ট
দেওয়া অনির্দেশিত গ্রাফে b নোড এবং a এজ থাকলে, অয়লার সার্কিট বানাতে ন্যূনতম কতগুলো এজ যোগ করতে হবে তা বের করুন।
ইনপুট
b = 3, a = 2 Edges[] = {{1, 2}, {2, 3}} আউটপুট
1
১ এবং ৩ কানেক্ট করলে অয়লার সার্কিট তৈরি হয়।
পদ্ধতি
অয়লার সার্কিট থাকতে হলে সব নোডের ডিগ্রি জোড় হতে হবে। দুটি কেস হতে পারে:
একটি কানেক্টেড কম্পোনেন্ট থাকলে
সব নোডের ডিগ্রি জোড় হলে ইতিমধ্যে অয়লার সার্কিট আছে, এজ যোগ লাগবে না। কিন্তু বিজোড় ডিগ্রি থাকলে এজ যোগ করতে হবে। বিজোড় ডিগ্রি ওয়ালা নোডগুলো জোড়া বাঁধে এজ দিলে সব নোডের ডিগ্রি জোড় হয়ে যাবে।
ডিসকানেক্টেড কম্পোনেন্ট থাকলে
কম্পোনেন্টগুলোকে অড এবং ইভেন হিসেবে মার্ক করুন। অড কম্পোনেন্ট = কমপক্ষে একটা বিজোড় ডিগ্রি নোড আছে। সব ইভেন কম্পোনেন্ট নেয়া যেন একটি চেইনে কানেক্ট করুন, এতে একটি অড কম্পোনেন্ট বने যাবে। তারপর সব অড কম্পোনেন্টকে সাইক্লিক অর্ডারে কানেক্ট করুন। এতে মোট এজ সংখ্যা = ইভেন কম্পোনেন্টের সংখ্যা + অড কম্পোনেন্টের সংখ্যা।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void dfs1(vector<int> g1[], int vis1[], int odd1[], int deg1[], int comp, int v){
vis1[v] = 1;
if (deg1[v]%2 == 1)
odd1[comp]++;
for (int u : g1[v])
if (vis1[u] == 0)
dfs1(g1, vis1, odd1, deg1, comp, u);
}
int minEdge1(int n, int m, int s1[], int d1[]){
vector<int> g1[n+1], e1, o1;
int deg1[n+1];
int vis1[n+1];
int odd1[n+1];
memset(deg1, 0, sizeof(deg1));
memset(vis1, 0, sizeof(vis1));
memset(odd1, 0, sizeof(odd1));
for (int i = 0; i < m; i++){
g1[s1[i]].push_back(d1[i]);
g1[d1[i]].push_back(s1[i]);
deg1[s1[i]]++;
deg1[d1[i]]++;
}
int ans = 0, comp = 0;
for (int i = 1; i <= n; i++){
if (vis1[i]==0){
comp++;
dfs1(g1, vis1, odd1, deg1, comp, i);
if (odd1[comp] == 0)
e1.push_back(comp);
else
o1.push_back(comp);
}
}
if (o1.size() == 0 && e1.size() == 1)
return 0;
if (o1.size() == 0)
return e1.size();
if (e1.size() != 0)
ans += e1.size();
for (int i : o1)
ans += odd1[i]/2;
return ans;
}
int main(){
int b = 3, a = 2;
int source1[] = { 1, 2 };
int destination1[] = { 2, 3 };
cout << minEdge1(b, a, source1, destination1) << endl;
return 0;
} আউটপুট
1
