使用 C++ 将无向图转换为有向图,使得不存在长度大于 1 的路径
在本教程中,我们将讨论一个将无向图转换为有向图的程序,使得不存在长度大于 1 的路径。
为此,我们会提供一个无向图。我们的任务是将该图转换为一个给定的有向图,且没有路径的长度大于 1。
示例
#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; }
输出
1 2 1 3 1 4
广告