二分图判定 hdu5285 wyh2000 and pupil-白红宇

二分图判定 hdu5285 wyh2000 and pupil

阅读量：4975 次

发布时间：2019-06-12

本文共 1540 字，大约阅读时间需要 5 分钟。

非常明显要求一个二分图。先构图。然后用精典的点染色的方法，求出二分图中两个图的节点数量

由于整个图中有非常多个通块，每一个通块都做一次二分图

合并的时候。把每一个二分图中节点多的那部分的数量累加，就得到了a答案

那么b就是总数减去a

这题本身不难，可是数据很贱，题目要求每组中必须有一个人，且m可能为0

所以，要进行两个特判

n<=1时，不可能每组至少1人，直接输出Poor wyh

m==0时，没有不论什么限制。可是b组至少要一个人。所以输出n-1 1(有无数人在这里wa了貌似kuangbin也是)

然后还可能爆栈(尽管终于測评里没有，，还好没这样出数据)

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long LL;typedef pair
            
              PII;#pragma comment(linker,"/STACK:102400000,102400000")const int MX = 100000 + 5;const int INF = 0x3f3f3f3f;int vis[MX];vector
             
              G[MX];bool DFS(int u, int c, int &a, int &b) { b++; if(c) a++; vis[u] = c; for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(vis[v] == c) return false; if(vis[v] == -1 && !DFS(v, c ^ 1, a, b)) return false; } return true;}int main() { int T, n, m; scanf("%d", &T); while(T--) { memset(vis, -1, sizeof(vis)); scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { G[i].clear(); } for(int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } if(n <= 1) { printf("Poor wyh\n"); continue; } if(m == 0) { printf("%d 1\n", n - 1); continue; } bool sign = true; int Max = 0; for(int i = 1; i <= n; i++) { int a = 0, b = 0; if(vis[i] == -1) { if(!DFS(i, 0, a, b)) { sign = false; break; } Max += max(a, b - a); } } if(!sign) printf("Poor wyh\n"); else { printf("%d %d\n", Max, n - Max); } } return 0;}