hdu 5285 wyh2000 and pupil (交叉染色法，二分图点集差最大)
题目链接：hdu 5285 题目lianjie
题意：给定n个小朋友，以及小朋友之间的关系，要求将小朋友分成两组，**并且每组至少一个人，**现在问能否这样分组，如果有解，输出两组的人数，并保证第一组的人数尽可能地大。
思路：。。。一开始看到n的数据范围。。。想当然的以为会给认识的人的关系。。。尼玛。。。求个补图就够受的了。。。。不会做，卒。
结果发现。。竟然给的是两个人不认识的关系。。。2333
那么我们来交叉染色。。。
实际上交叉染色的过程中，颜色相同的点属于二分图中相同的点集合。
交叉染色其实是在模拟交错轨的过程...？
由于图不一定联通，可能由多个联通块。
我们在交叉染色的时候记录一下0,1的个数（也就是两个点集的大小）
然后每次把大的累加（因为没说不认识的就是默认认识了。。。）
无解的情况有：任何一个联通快无解或者n<=1
此外还需要注意，m可能为0.
特判一下，m为0或者为1，直接输出n-1和1.
以及！
n<=1的无解是在特判m之前的。。。。我好傻啊。
n<=1的无解是在特判m之前的。。。。我好傻啊。
n<=1的无解是在特判m之前的。。。。我好傻啊。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年09月02日 星期五 14时41分35秒
4File Name :code/hdu/5285.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int M = 2E5+7;
32const int N = 1E5+7;
33int n,m;
34int head[N];
35int col[N];
36struct Edge
37{
38 int v;
39 int nxt;
40}edge[M];
41int cnt;
42int cnt0,cnt1;
43void addedge(int u ,int v)
44{
45 edge[cnt].v = v;
46 edge[cnt].nxt = head[u];
47 head[u] = cnt;
48 cnt++;
49}
50int dfs( int u,int x,int fa)
51{
52 col[u] = x;
53 if (x==0) cnt0++;else cnt1++;
54 for ( int i = head[u] ; i !=-1 ; i = edge[i].nxt)
55 {
56 int v = edge[i].v;
57 if (v==fa) continue;
58 if (col[v]==1-x) continue;
59 if (col[v]==x) return -1;
60 if (!dfs(v,1-x,u)) return -1;
61 }
62 return max(cnt0,cnt1);
63}
64int solve()
65{
66 int res = 0 ;
67 for ( int i = 1 ; i <= n ; i++)
68 {
69 if (col[i]!=-1) continue;
70 cnt0 = cnt1 = 0 ;
71 int tmp = dfs(i,0,-1);
72 if (tmp==-1) return -1;
73 res+=tmp;
74 }
75 return res;
76}
77int main()
78{
79 #ifndef ONLINE_JUDGE
80 freopen("code/in.txt","r",stdin);
81 #endif
82 int T;
83 cin>>T;
84 while (T--)
85 {
86 scanf("%d%d",&n,&m);
87 cnt = 0 ;
88 ms(head,-1);
89 ms(col,-1);
90 for ( int i = 1 ; i <= m ; i++)
91 {
92 int u,v;
93 scanf("%d%d",&u,&v);
94 addedge(u,v);
95 addedge(v,u);
96 }
97 if (n<2)
98 {
99 puts("Poor wyh");
100 continue;
101 }
102 if (m<=1)
103 {
104 printf("%d %d\n",n-1,1);
105 continue;
106 }
107 int ans = solve();
108 if (ans==-1) puts("Poor wyh");
109 else printf("%d %d\n",ans,n-ans);
110 }
111 #ifndef ONLINE_JUDGE
112 fclose(stdin);
113 #endif
114 return 0;
115}