資料結構
網路
關係型資料庫管理系統
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會科學
時尚科學
法律科學使用 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
更新時間： 2020 年 1 月 22 日
155 次瀏覽
廣告