แปลง Undirected Graph เป็น Directed Graph ไม่มี Path ยาวกว่า 1 ใน C++

ภาพรวมปัญหา

แปลง Undirected Graph เป็น Directed Graph โดยที่ไม่มี Path ความยาว > 1

วิธีแก้ปัญหา (Bipartite Check)

1. ตรวจสอบว่า Graph เป็น Bipartite ได้หรือไม่ (2-Colorable)
2. ถ้าเป็น → Direct Edge จาก Color 0 ไป Color 1
3. ถ้าไม่เป็น → พิมพ์ -1

ตัวอย่างโค้ด C++

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

#define N 100005
vector<int> gr[N];
int colour[N];
vector<pair<int, int>> edges;
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;
}

ผลลัพธ์ (Output)

1 2
1 3
1 4