Description
Wyh2000 has n pupils.Id of them are from to
.In order to increase the cohesion between pupils,wyh2000 decide to divide them into 2 groups.Each group has at least 1 pupil.
Now that some pupils don't know each other(if doesn't know
,then
doesn't know
).Wyh2000 hopes that if two pupils are in the same group,then they know each other,and the pupils of the first group must be as much as possible.
Please help wyh2000 determine the pupils of first group and second group. If there is no solution, print "Poor wyh".
Input
For each case, the first line contains two integers indicate the number of pupil and the number of pupils don't konw each other.
In the next m lines,each line contains 2 intergers <
,indicates that
don't know
and
don't know
,the pair
will only appear once.
Output
Sample Input
2
8 5
3 4
5 6
1 2
5 8
3 5
5 4
2 3
4 5
3 4
2 4
Sample Output
5 3
Poor wyh
/*/
二分图染色法判定 题解： 把两个相连的点标记颜色为不同颜色1和0，表示两位同学相互不认识； 统计两个颜色的个数。 注意，应为可能出现多个联通块的情况，这时候只要将各个联通块的最少的颜色 加起来，用总人数减去这个和就是人数最多那个组的人数了。 本题还要注意几个特判。 AC代码：
/*/
#include"algorithm"
#include"iostream"
#include"cstring"
#include"cstdlib"
#include"string"
#include"cstdio"
#include"vector"
#include"cmath"
#include"queue"
using namespace std;
#define memset(x,y) memset(x,y,sizeof(x))
#define memcpy(x,y) memcpy(x,y,sizeof(x))
#define MX 500005 struct Edge {
int v,nxt;
} E[MX*2]; int col[3]; int Head[MX],erear; void edge_init() {
erear=0;
memset(E,0);
memset(Head,-1);
}
void edge_add(int u,int v) {
E[erear].v=v;
E[erear].nxt=Head[u];
Head[u]=erear++;
} int color[MX];
bool DFS(int u,int c) {
color[u]=c;
if(color[u]==1) {
col[1]++;
} else col[0]++;
for(int i=Head[u]; ~i; i=E[i].nxt) {
int v=E[i].v;
if(color[v]!=-1&&color[u]==color[v]) return 0;
else if(color[v]==-1) {
if(DFS(v,c^1)==0) return 0;
}
}
return 1;
} int main() {
int n,m;
int T;
cin>>T;
while(T--) {
scanf("%d%d",&n,&m);
edge_init();
for(int i=1; i<=m; i++) {
int u,v;
scanf("%d%d",&u,&v);
edge_add(u,v);
edge_add(v,u);
}
if(n<2) {
puts("Poor wyh");
continue;
}
if(!m) {
printf("%d 1\n",n-1);
}
memset(color,-1);
bool sign=1;
int minn=0;
for(int i=1; i<=n; i++) {
if(color[i]==-1) {
memset(col,0);
sign=DFS(i,0);
minn+=min(col[0],col[1]);
if(!sign)break;
} }
if(!sign)puts("Poor wyh") ;
else printf("%d %d\n",n-minn,minn);
}
return 0;
}