Chuyển Đồ Thị Vô Hướng Thành Có Hướng Không Có Đường Dài Hơn 1 Trong C++

Trong hướng dẫn này, chúng ta sẽ thảo luận chương trình chuyển đổi đồ thị vô hướng thành đồ thị có hướng sao cho không có đường đi nào dài hơn 1.

Cho một đồ thị vô hướng. Nhiệm vụ là chuyển đổi thành đồ thị có hướng với điều kiện không đường đi nào có độ dài lớn hơn 1.

Ví Dụ

#include <bits/stdc++.h>
using namespace std;
#define N 100005

// Lưu đồ thị
vector<int> gr[N];
// Lưu màu của mỗi đỉnh
int colour[N];
vector<pair<int, int>> edges;
bool bip;

// Thêm cạnh vào đồ thị
void add_edge(int x, int y) {
    gr[x].push_back(y);
    gr[y].push_back(x);
    edges.push_back(make_pair(x, y));
}

// Kiểm tra đồ thị hai phía (bipartite)
void dfs(int x, int col) {
    colour[x] = col;
    // Duyệt các đỉnh con
    for (auto i : gr[x]) {
        if (colour[i] == -1)
            dfs(i, col ^ 1);
        // Nếu con và cha cùng màu
        else if (colour[i] == col)
            bip = false;
    }
}

// Chuyển thành đồ thị có hướng
void convert_directed(int n, int m) {
    memset(colour, -1, sizeof(colour));
    bip = true;
    // Gọi hàm kiểm tra bipartite
    dfs(1, 1);
    if (!bip) {
        cout << -1;
        return;
    }
    // Nếu bipartite được
    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