题目大意
有 n(1≤n≤3*105) 匹马，每条马都有几个敌人（不超过 3 个），现在要求把这些马分成两部分（允许一部分中没有一条马），使得对于每条马，和它在同一部分中的敌人的数量不超过1个
给出了所有的敌对关系，求一个划分的方案。如果不存在划分方案，输出-1
做法分析
首先，观察下为什么题目给的数据范围这么奇葩：
每条马的敌人的数量不超过 3 个
这有什么用呢？想了很久，画了好几个图，最终确定，这样的条件下，一定是存在一个划分方案，使得每部分中，每条马的敌人数量不超过 1 个。
可以考虑 4 个点的完全图，每个点的度是 3，对应了 3 个敌人，我们完全可以找出一种分配的方案使得这个图的点分成两个点集，那么，对于其余的情况，肯定也是能够找出一种解的，因为他们的关系比 4 个点的完全图的关系更加的简单
也就是说，输出 -1 的情况是不存在的
接下来就考虑怎么构造出一种分配的方案了
实在是想不出有什么其他的做法了，干脆贪心的找找，类似于 SPFA 的 BFS：
①. 先假设所有的马都在同一个部分中，把所有不合格的马（有超过 1 个敌人的）入队
②. BFS 的过程中，先把当前马移动到另一个部分中，然后再统计它的敌人中，哪些马变得不合法了，把不合法的加入到队列中
这样不断的 BFS，肯定能够找到一种分配方案，但是具体的时间复杂度不知道怎么计算的，迷迷糊糊的就过了......
参考代码
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <queue> 5 6 using namespace std; 7 8 const int N=300006; 9 10 int arc[N][10], n, m, ans[N]; 11 queue <int> q; 12 13 bool Ok(int u) 14 { 15 int cnt=0; 16 for(int i=1; i<=arc[u][0]; i++) 17 { 18 int v=arc[u][i]; 19 if(ans[u]==ans[v]) cnt++; 20 } 21 return cnt<2; 22 } 23 24 void BFS() 25 { 26 while(!q.empty()) q.pop(); 27 for(int i=1; i<=n; i++) 28 if(!Ok(i)) q.push(i); 29 while(!q.empty()) 30 { 31 int u=q.front(); 32 q.pop(); 33 if(Ok(u)) continue; 34 ans[u]^=1; 35 for(int i=1; i<=arc[u][0]; i++) 36 if(!Ok(arc[u][i])) q.push(arc[u][i]); 37 } 38 } 39 40 int main() 41 { 42 scanf("%d%d", &n, &m); 43 for(int i=1; i<=n; i++) ans[i]=0, arc[i][0]=0; 44 for(int i=0, a, b; i<m; i++) 45 { 46 scanf("%d%d", &a, &b); 47 arc[a][++arc[a][0]]=b; 48 arc[b][++arc[b][0]]=a; 49 } 50 BFS(); 51 for(int i=1; i<=n; i++) printf("%d", ans[i]); 52 printf("\n"); 53 return 0; 54 }