解题思路
数据范围不是很大，那应该不是那些普遍的图论的算法。考虑搜索，用暴力解决。从1到N枚举每一个点的位置，搜索这个点事选还是不选。如果在这个点之前选到的点中又和他冲突的点，那就不选，要么就选。
附上代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n, m, cnt[
103], Ans[
103], ans[
103], res;
bool dis[
103][
103], mark;
inline void DFS(
int x,
int tot) {
if(x == n+
1) {
if(res <
tot) {
res =
tot;
for(
int i=
1; i<=n; i++
)
Ans[i] =
ans[i];
}
return ;
}
if(tot + (n-x+
1) <= res)
return ;
mark =
false;
for(
int i=
1; i<=x-
1; i++
) {
if(ans[i] && (dis[x][i] ||
dis[i][x])) {
mark =
true;
break;
}
}
if(!
mark) {
ans[x] =
1;
DFS(x+
1, tot+
1);
ans[x] =
0;
}
DFS(x+
1, tot);
}
int main() {
scanf("%d%d", &n, &
m);
int x, y;
for(
int i=
1; i<=m; i++
) {
cin>>x>>
y;
dis[x][y] =
1;
dis[y][x] =
1;
}
DFS(1,
0);
printf("%d\n", res);
for(
int i=
1; i<=n; i++) printf(
"%d ", Ans[i]);
}
转载于:https://www.cnblogs.com/bljfy/p/9463825.html
相关资源：锣鼓声声迎新春——新年工作计划ppt模板.zip
