图的 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
创建日期: 2024年1月2日 19:47:42