এই টিউটোরিয়ালে আমরা অনির্দেশিত গ্রাফকে নির্দেশিত গ্রাফে কনভার্ট করার প্রোগ্রাম নিয়ে আলোচনা করব যাতে কোনো পথের দৈর্ঘ্য ১-এর চেয়ে বড় নাও হয়।
এখানে আমাদের একটি অনির্দেশিত গ্রাফ দেওয়া থাকবে। আমাদের কাজ সেটিকে একটি নির্দেশিত গ্রাফে কনভার্ট করা যাতে কোনো পথের দৈর্ঘ্য ১-এর চেয়ে বড় না হয়।
বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
#define N 100005
// গ্রাফ সংরক্ষণ
vector<int> gr[N];
// প্রতিটি ভার্টেক্সের রঙ সংরক্ষণ
int colour[N];
vector<pair<int, int> > edges;
bool bip;
// গ্রাফে এজ যোগ করা
void add_edge(int x, int y) {
gr[x].push_back(y);
gr[y].push_back(x);
edges.push_back(make_pair(x, y));
}
// দেওয়া গ্রাফ বাইপার্টাইট কিনা চেক করা
void dfs(int x, int col) {
colour[x] = col;
// চাইল্ড ভার্টেক্সে যাওয়া
for (auto i : gr[x]) {
if (colour[i] == -1)
dfs(i, col ^ 1);
// যদি চাইল্ড ও পেরেন্ট একই ব্রাঞ্চে থাকে
else if (colour[i] == col)
bip = false;
}
}
// নির্দেশিত গ্রাফে কনভার্ট করা
void convert_directed(int n, int m) {
memset(colour, -1, sizeof colour);
bip = true;
// বাইপার্টাইট ফাংশন কল
dfs(1, 1);
if (!bip) {
cout << -1;
return;
}
// যদি বাইপার্টাইট সম্ভব হয়
for (int i = 0; i < m; i++) {
if (colour[edges[i].first] == 0)
swap(edges[i].first, edges[i].second);
cout << edges[i].first << " " << edges[i].second << endl;
}
}
int main() {
int n = 4, m = 3;
add_edge(1, 2);
add_edge(1, 3);
add_edge(1, 4);
convert_directed(n, m);
return 0;
}
আউটপুট
1 2 1 3 1 4
