zjoj_4551_Even separation

题目：
这里写图片描述

输入：
4 6
1 2
1 3
1 4
2 3
2 4
3 4

输出：
YES
BAAA

题解：
建异或方程组，每个点可以赋值0或1，如果一个点原来的度数是偶数，那么它领域的点的异或要是0；如果一个点原来的度数是奇数，那么它领域的点异或上它自己要是1。高斯消元。
详细的题解

代码：

 1 #include <stdio.h>      
 2 #include <iostream>      
 3 #include <algorithm>      
 4 #include <sstream>      
 5 #include <stdlib.h>      
 6 #include <string.h>      
 7 #include <limits.h>      
 8 #include <string>      
 9 #include <time.h>      
10 #include <math.h>      
11 #include <queue>      
12 #include <stack>      
13 #include <map>   
14 using namespace std;
15 typedef long long ll;
16 
17 int a[501][501],du[501],b[501];
18 int n,m;
19 
20 void init(){
21     int x,y;
22     cin>>n>>m;
23     for (int i=1;i<=m;i++){
24         cin>>x>>y;
25         du[x]++; du[y]++;
26         a[x][y]=1; a[y][x]=1;
27     }
28     for (int i=1;i<=n;i++)
29         if (du[i]%2==1){
30             b[i]=1; a[i][i]=1;
31         } else b[i]=0;
32 }
33 
34 void gsxy(){
35     for (int i=1;i<=n;i++){
36         int k=i;
37         for (int j=i+1;j<=n;j++)
38             if (a[j][i]) k=j;
39         for (int j=1;j<=n;j++){
40             int t=a[i][j];
41             a[i][j]=a[k][j];
42             a[k][j]=t;
43         }
44         int t=b[i]; b[i]=b[k]; b[k]=t;
45         for (int j=1;j<=n;j++){
46             if ((j==i)||(!a[j][i])) continue;
47             b[j]^=b[i];
48             for (int k=1;k<=n;k++)
49                 a[j][k]^=a[i][k];
50         }
51     }
52 }
53 
54 int main(){
55     init();
56     gsxy();
57     int bo=0;
58     for (int i=1;i<=n;i++)
59         if (b[i]) bo++;
60     if ((bo==n)||(!bo)){
61         cout<<"NO"<<endl;
62         return 0;
63     }
64     cout<<"YES"<<endl;
65     for (int i=1;i<=n;i++)
66         if (b[i]) cout<<"B"; 
67         else cout<<"A";
68     return 0;
69 }