इस ट्यूटोरियल में, हम अनडायरेक्टेड ग्राफ को डायरेक्टेड ग्राफ में बदलने के प्रोग्राम पर चर्चा करेंगे जिससे कोई पाथ लंबाई 1 से अधिक न हो।
इसके लिए हमें एक अनडायरेक्टेड ग्राफ दिया जाएगा। हमारा कार्य उस ग्राफ को डायरेक्टेड ग्राफ में बदलना है बशर्ते कोई पाथ की लंबाई 1 से अधिक न हो।
उदाहरण
#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
