hdu 5285 wyh2000 and pupil 二分图染色发判定，求最大匹配

墨蓝 2022-08-02 12:46 82阅读 0赞

# 染色法判定是不是二分图，如果是二分图，每个相邻的点都可以染成不相同的颜色，如果存在有两个点相邻并且颜色相同，则构不成二分图。这题构成二分图有很多种情况，贪心的选择使得第一组的人数最多就行。注意如果第二组人数至少要为一。    #

#     #

# wyh2000 and pupil #

Accepts: 93

Submissions: 925

Time Limit: 3000/1500 MS (Java/Others)

Memory Limit: 131072/65536 K (Java/Others)

问题描述

青年理论计算机科学家wyh2000在教导他的小学生。
    共有
      
       n
      个小学生，编号为
      
       1−n
      。为了增加小学生之间的凝聚力，wyh2000决定将所有小学生分成
      
       2
      组，每组都至少有
      
       1
      个人。
    但是有些小学生之间并不认识，而且如果
      
       a
      不认识
      
       b
      ，那么
      
       b
      也不认识
      
       a
      。
    Wyh2000希望每组中的小学生都互相认识。而且第一组的人要尽可能多。
    请你帮wyh2000求出第一组和第二组的人数是多少。如果找不到分组方案，则输出"Poor wyh"。

输入描述

第一行一个数
      
       T
      ，表示数据组数。
    对于每组数据，第一行两个数
      
       n,m
      ，表示小学生数量和互相不认识的小学生的数量。
    接下来
      
       m
      行，每行两个数
      
       x,y(x<y)
      ，表示
      
       x
      不认识
      
       y
      ，
      
       y
      不认识
      
       x
      。保证一对
      
       (x,y)
      只会出现一次。
    
      
       T≤10,0≤n,m≤100000

输出描述

对于每组数据，输出答案。

输入样例

2
    8 5
    3 4
    5 6
    1 2
    5 8
    3 5
    5 4
    2 3
    4 5
    3 4
    2 4

输出样例

5 3
    Poor wyh

代码是参照了别人的。

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    
    vector<int> v[100010];
    int color[100010];
    bool flag=1;
    
    int a[2];           //a数组代表每次染色分成两组的人数
    int ans1,ans2;
    void dfs(int x)
    {
        a[color[x]-1]++;                    //如果color[x]是颜色1，则第一组人数加一，如果是颜色二，第二组人数加一
        for(int i=0;i<(int)v[x].size();i++)
        {
            int t=v[x][i];
            if(color[t]==0)
            {
                color[t]=(3-color[x]);   //当前颜色取跟上一个颜色相反的颜色
                dfs(t);                  //从前点在进行染色
            }
            else if(color[t]==color[x])
            {
                flag=0;                  //如果存在当前颜色与前面相邻颜色一样，则不能构成二分图
            }
        }
    }
    int main()
    {
        int T=in();
        while(T--)
        {
            int n=in(),m=in();
            int t1,t2;
            ans1=0,ans2=0;
            for(int i=0;i<=n;i++)
            {
                v[i].clear();
            }
            mem(color,0);
            flag=1;   //注意每次初始化
            for(int i=0;i<m;i++)
            {
                t1=in(),t2=in();
                v[t1].push_back(t2);
                v[t2].push_back(t1);
            }
            if(n<2)
            {
                puts("Poor wyh");
                continue;
            }
            int ans=0;
            for(int i=1;i<=n;i++)
            {
    
                if(!color[i])
                {
                    a[0]=a[1]=0;
                    color[i]=1;
                    dfs(i);
                    ans += max(a[0],a[1]);//贪心的取最大的一组
                }
            }
            if(flag)
            {
                if(ans==n)ans--;
                printf("%d %d\n",ans,n-ans);
            }
            else puts("Poor wyh");
        }
        return 0;
    }