Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình chuyển đổi đồ thị vô hướng thành đồ thị có hướng sao cho không có đường dẫn nào có độ dài lớn hơn 1.
Đối với điều này, chúng tôi sẽ được cung cấp với một đồ thị vô hướng. Nhiệm vụ của chúng ta là chuyển đổi biểu đồ đó thành một biểu đồ trực tiếp vì không có đường dẫn nào có độ dài lớn hơn 1.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
#define N 100005
//storing the graph
vector<int> gr[N];
//storing colour of each vertex
int colour[N];
vector<pair<int, int> > edges;
bool bip;
//adding edges to the graph
void add_edge(int x, int y){
gr[x].push_back(y);
gr[y].push_back(x);
edges.push_back(make_pair(x, y));
}
//checking if the given graph
//is bipartite
void dfs(int x, int col){
colour[x] = col;
//moving to the child vertices
for (auto i : gr[x]) {
if (colour[i] == -1)
dfs(i, col ^ 1);
//if child and parent having
//same branch
else if (colour[i] == col)
bip = false;
}
}
//converting into direct graph
void convert_directed(int n, int m){
memset(colour, -1, sizeof colour);
bip = true;
//calling bipartite function
dfs(1, 1);
if (!bip) {
cout << -1;
return;
}
//if bipartite is possible
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;
} Đầu ra
1 2 1 3 1 4