【正经题解】部落卫队
2024-02-21 14:34:47
发布于:浙江
13阅读
0回复
0点赞
#include <iostream>
#define MAX_VALUE int
#define SIZE 110
using namespace std;
MAX_VALUE graph[SIZE][SIZE], result[SIZE], tempResult[SIZE];
MAX_VALUE total = 0, currentTotal = 0, numVertices, numEdges;
// 深度优先搜索函数
void dfs(MAX_VALUE vertex) {
if (vertex > numVertices) {
// 如果当前总值小于等于之前的最大总值,则返回
if (currentTotal <= total) {
return;
}
// 更新最大总值,并复制当前结果到最终结果数组
total = currentTotal;
for (MAX_VALUE i = 1; i <= numVertices; i++) {
result[i] = tempResult[i];
}
return;
}
bool isValidVertex = true;
// 检查是否满足条件,如果与之前选择的节点存在边且已经选择了该节点,则无效
for (MAX_VALUE i = 1; i < vertex; i++) {
if (graph[i][vertex] && tempResult[i]) {
isValidVertex = false;
break;
}
}
// 如果当前节点满足条件,则选择该节点,并递归搜索下一个节点
if (isValidVertex) {
tempResult[vertex] = 1;
currentTotal++;
dfs(vertex + 1);
tempResult[vertex] = 0;
currentTotal--;
}
dfs(vertex + 1);
}
int main() {
cin >> numVertices >> numEdges;
for (MAX_VALUE i = 1; i <= numEdges; i++) {
MAX_VALUE u, v;
cin >> u >> v;
// 构建无向图,将边的连接关系设置为1
graph[u][v] = graph[v][u] = 1;
}
dfs(1);
cout << total << '\n';
for (MAX_VALUE j= 1;j<=numVertices;j++) {
cout << result[j] << ' ';
}
return 0;
}
这里空空如也
有帮助,赞一个