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之前的。。。。我好傻啊。
/* ***********************************************
Author :111qqz
Created Time :2016年09月02日 星期五 14时41分35秒
File Name :code/hdu/5285.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int M = 2E5+7;
const int N = 1E5+7;
int n,m;
int head[N];
int col[N];
struct Edge
{
int v;
int nxt;
}edge[M];
int cnt;
int cnt0,cnt1;
void addedge(int u ,int v)
{
edge[cnt].v = v;
edge[cnt].nxt = head[u];
head[u] = cnt;
cnt++;
}
int dfs( int u,int x,int fa)
{
col[u] = x;
if (x==0) cnt0++;else cnt1++;
for ( int i = head[u] ; i !=-1 ; i = edge[i].nxt)
{
int v = edge[i].v;
if (v==fa) continue;
if (col[v]==1-x) continue;
if (col[v]==x) return -1;
if (!dfs(v,1-x,u)) return -1;
}
return max(cnt0,cnt1);
}
int solve()
{
int res = 0 ;
for ( int i = 1 ; i <= n ; i++)
{
if (col[i]!=-1) continue;
cnt0 = cnt1 = 0 ;
int tmp = dfs(i,0,-1);
if (tmp==-1) return -1;
res+=tmp;
}
return res;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif
int T;
cin>>T;
while (T--)
{
scanf("%d%d",&n,&m);
cnt = 0 ;
ms(head,-1);
ms(col,-1);
for ( int i = 1 ; i <= m ; i++)
{
int u,v;
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
if (n<2)
{
puts("Poor wyh");
continue;
}
if (m<=1)
{
printf("%d %d\n",n-1,1);
continue;
}
int ans = solve();
if (ans==-1) puts("Poor wyh");
else printf("%d %d\n",ans,n-ans);
}
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}