You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
41 lines
973 B
C++
41 lines
973 B
C++
#define _CRT_SECURE_NO_WARNINGS
|
|
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
int mp[101][101], n, m, ans = 0x3f3f3f3f;
|
|
int arr[101][101];
|
|
int cnt[101];
|
|
|
|
void dfs(int p, int r) {
|
|
if (r >= ans) return;
|
|
if (p > n)
|
|
ans = min(ans, r);
|
|
else {
|
|
for (int i = 1; i <= r; i++) {
|
|
bool flag = true;
|
|
for (int j = 0; j < cnt[i] && flag; j++)
|
|
if (mp[p][arr[i][j]])
|
|
flag = false;
|
|
if (flag) {
|
|
arr[i][cnt[i]++] = p;
|
|
dfs(p + 1, r);
|
|
cnt[i]--;
|
|
}
|
|
}
|
|
arr[r + 1][cnt[r + 1]++] = p;
|
|
dfs(p + 1, r + 1);
|
|
cnt[r + 1]--;
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
scanf("%d%d", &n, &m);
|
|
for (int i = 0, a, b; i < m; i++)
|
|
scanf("%d%d", &a, &b), mp[a][b] = mp[b][a] = 1;
|
|
dfs(1, 0);
|
|
printf("%d", ans);
|
|
return 0;
|
|
}
|