在 C++ 中将无向图转换为有向图，使得没有长度大于 1 的路径
c++server side programmingprogramming
在本教程中，我们将讨论一个将无向图转换为有向图的程序，使得没有长度大于 1 的路径。
为此，我们将提供一个无向图。我们的任务是将该图转换为有向图，前提是没有路径的长度大于 1。
示例
#include <bits/stdc++.h>
using namespace std;
#define N 100005
//存储图
vector<int> gr[N];
//存储每个顶点的颜色
int colour[N];
vector<pair<int, int> > edge;
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
