猜结论 + bitset优化高斯消元：CF1070L

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135202185

https://www.luogu.com.cn/problem/CF1070L

所有点度数为偶，则答案为1.

此时可以猜结论，猜测答案最多为2.

如果答案为2，看一下充要条件是什么。划分为两个集合（注意可以不连通），其中一个 $x_i=1$ ，另一个为0.

如果本身度数为偶，则是 $\oplus x_j=0$ 。如果度数为奇，则 $x_i\oplus x_j=1$ 。这可以列出 $n$ 条方程，直接高斯消元解是 $O(n^3)$ ，但因为只有0/1，所以可以bitset优化。

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//srand(time(0));
#define N 2010
//#define M
//#define mo
int n, m, i, j, k, T;
int c[N], u, v, ans[N]; 
bitset<N>g[N]; 

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
	T=read();
	while(T--) {
		n=read(); m=read(); 
		for(i=1; i<=n; ++i) g[i].reset(), c[i]=0; 		
		for(i=1; i<=m; ++i) {
			u=read(); v=read(); 
			++c[u]; ++c[v]; 
			g[u][v] = g[v][u] = 1; 
		}
		for(i=1; i<=n; ++i) if(c[i] & 1) break; 
		if(i > n) { printf("1\n"); for(i=1; i<=n; printf("1 "), ++i); puts(""); continue; }
		for(i=1; i<=n; ++i) if(c[i] & 1) g[i][n+1]=1, g[i][i]=1; 
		for(i=1; i<=n; ++i) {
			for(j=i; j<=n; ++j) if(g[j][i]) break; 
			swap(g[i], g[j]); 
			for(j=i+1; j<=n; ++j) if(g[j][i]) g[j]^=g[i]; 
		}
		for(i=n; i>=1; --i) {
			ans[i] = g[i][n+1]; 
			for(j=i+1; j<=n; ++j) ans[i]^=(g[i][j]*ans[j]); 
		}
		puts("2"); 
		for(i=1; i<=n; ++i) printf("%d ", ans[i]+1); 	
		puts(""); 
	}
	return 0;
}