图的 m 着色问题

class Color {
    friend int mColoring(int , int, int**);
private:
    bool Ok(int k);
    void Backtrack(int t);
    int n, m, **a, *x;
    long sum;
};

bool Color::Ok(int k) {
    for (int j = 1; j < k; j++) {
        if (a[k][j] && x[j] == x[k]) {
            return false;
        }
    }
    return true;
}

void Color::Backtrack(int t) {
    if (t > n) {
        sum++;
        for (int i = 1; i <= n; i++) {
            cout << x[i] << " ";
        }
        cout << endl;
    } else {
        for (int i = 1; i <= m; i++) {
            x[t] = i;
            if (Ok(t)) {
                Backtrack(t + 1);
            }
            x[t] = 0;
        }
    }
}

int mColoring(int n, int m, int **a) {
    Color X;
    X.n = n;
    X.m = m;
    X.a = a;
    X.sum = 0;
    int *p = new int[n + 1];
    for (int i = 0; i <= n; i++)
        p[i] = 0;
    X.x = p;
    X.Backtrack(1);
    delete [] p;
    return X.sum;
}

最后更新: 2024年1月14日 18:59:58
创建日期: 2024年1月2日 19:47:42
回到页面顶部