CF1070L Odd Federalization 高斯消元

传送门

---

\(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;

}