傳送門

---

\(r = 1\)直接判斷所有點度數是否為偶數

考慮\(r = 2\)的情況。設\(x_i=0/1\)表示\(i\)點所在的集合，那么若\(2 \mid du_u\)，則\(\bigoplus\limits_{(u,v) \in e} x_v = 0\)，否則\(\bigoplus\limits_{(u,v) \in e} x_v = x_u \bigoplus 1\)，即\(x_u\ \ xor\ \ \bigoplus\limits_{(u,v) \in e} x_v = 1\)。

可以發現上面是一個異或方程組，高斯消元解出來即可。

但是\(r\)有可能\(> 2\)嗎？事實上\(r\)只會等于\(1\)或者\(2\)。

可以發現如果\(r>2\)，意味著上面的異或方程組無解。無解則存在某些異或方程能夠異或得到\(0=1\)。右式為\(1\)意味著有奇數個入度為奇數的點，而左式為\(0\)意味著所有點在這些異或方程中都出現了偶數次，而度數為奇數的點會在自己的方程中出現一次，所以在這個導出子圖中，度數為奇數的點連接了奇數個點，度數為偶數的點連接了偶數個點，這意味著這個導出子圖的度數和為奇數。但對于一個無向圖度數無論如何都是偶數，所以不存在無解情況，所以\(r \leq 2\)。

#include<bits/stdc++.h> using namespace std;inline int read(){int a = 0;char c = getchar();bool f = 0;while(!isdigit(c)){if(c == '-')f = 1;c = getchar();}while(isdigit(c)){a = (a << 3) + (a << 1) + (c ^ '0');c = getchar();}return f ? -a : a; }const int MAXN = 2010; bitset < MAXN > gauss[MAXN]; int N , M , ans[MAXN];int main(){for(int T = read() ; T ; --T){N = read();M = read();for(int i = 1 ; i <= N ; ++i){gauss[i].reset();gauss[i].set(i);}for(int i = 1 ; i <= M ; ++i){int a = read() , b = read();gauss[a][N + 1] = ~gauss[a][N + 1];gauss[b][N + 1] = ~gauss[b][N + 1];gauss[a][b] = gauss[b][a] = 1;}bool f = 1;for(int i = 1 ; f && i <= N ; ++i)f = !gauss[i][N + 1];if(f){puts("1");for(int i = 1 ; i <= N ; ++i)printf("1 ");}else{for(int i = 1 ; i <= N ; ++i)if(!gauss[i][N + 1])gauss[i][i] = 0;int now = 1;for(int i = 1 ; i <= N ; ++i){int j = now;while(j <= N && !gauss[j][i])++j;if(j > N){ans[i] = 0;for(int k = 1 ; k < now ; ++k)gauss[k][i] = 0;continue;}if(j != now)swap(gauss[j] , gauss[now]);while(++j <= N)if(gauss[j][i])gauss[j] ^= gauss[now];++now;}for(int j = now - 1 ; j ; --j){int p = 0;for(int k = 1 ; !p && k <= N ; ++k)if(gauss[j][k])p = k;ans[p] = gauss[j][N + 1];for(int k = j - 1 ; k ; --k)if(gauss[k][p])gauss[k] ^= gauss[j];}puts("2");for(int i = 1 ; i <= N ; ++i)printf("%d " , ans[i] + 1);}putchar('\n');}return 0; }

轉載于:https://www.cnblogs.com/Itst/p/10423837.html

總結

以上是生活随笔為你收集整理的CF1070L Odd Federalization 高斯消元的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。