rt

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>

using namespace std;

const int maxn = 105;
int a[maxn][maxn];
int ans[maxn];
int n, m;

void print()
{
	puts("");
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n + 1; j++)
		{
			printf("%5d ", a[i][j]);
		}
		puts("");
	}
	puts("");
}

void print_ans()
{
	puts("");
	for (int i = 1; i <= n; i++)
	{
		cout << ans[i] << " ";
	}
	puts("");
}

int ansd = 1e9;

void dfs(int k, int tot)
{
	if (tot > ansd) return;
	if (k == 0)
	{
		ansd = min(ansd, tot);
		return;
	}
	if (a[k][k])
	{
		ans[k] = a[k][n + 1];
		for (int j = n; j >= k; j--)
		{
			ans[k] ^= ans[j] & a[k][j];
		}
		if (ans[k]) dfs(k - 1, tot + 1);
		else dfs(k - 1, tot);
	}
	else
	{
		ans[k] = 0, dfs(k - 1, tot);
		ans[k] = 1, dfs(k - 1, tot + 1);
	}
}

void gauss()
{
	// row 行 col 列
	int row = 1, col = 1;
	for (col = 1; col <= n; col++)
	{
		int t = row;
		for (int i = t; i <= n; i++)
		{
			if (a[i][col] == 1)
			{
				t = i;
				break;
			}
		}
//		if (a[t][col] == 0) continue;
		swap(a[t], a[row]);

		for (int i = row + 1; i <= n; i++)
		{
			if (!a[i][col]) continue;
			for (int j = n + 1; j >= col; j--)
			{
				a[i][j] ^= a[row][j];
			}
		}
		row++;
	}
	if (row <= n)
	{
		return ;
	}
	for (int i = n; i >= 1; i--)
	{
		ans[i] = a[i][n + 1];
		for (int j = i + 1; j <= n; j++)
		{
			if (a[i][j]) ans[i] ^= ans[j];
		}
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++)
	{
		cnt += ans[i] == 1;
	}
	cout << cnt << endl;
	exit(0);
}

int main()
{
#ifndef ONLINE_JUDGE
#define LOCAL
//	freopen("in.txt", "r", stdin);
#endif
	cin >> n >> m;
	for (int i = 1, u, v; i <= m; i++)
	{
		cin >> u >> v;
		a[u][v] = 1, a[v][u] = 1;
	}
	for (int i = 1; i <= n; i++) a[i][i] = 1, a[i][n + 1] = 1;
	gauss();
	dfs(n, 0);
	cout << ansd << endl;
#ifdef LOCAL
	fprintf(stderr, "%f\n", 1.0 * clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}

数据#12:

16 45
7 8
4 15
11 9
12 7
16 10
6 11
5 9
4 12
10 4
15 12
1 6
6 13
7 15
6 5
4 14
11 10
13 8
1 14
3 12
7 2
4 6
16 1
10 8
10 15
2 4
16 9
10 1
14 6
16 6
13 1
8 16
9 10
3 2
10 7
14 15
4 9
14 10
5 16
3 5
9 12
16 2
12 6
13 9
3 11
12 16

ans:

8