Codeforces 435 B Mahmoud and Ehab and the bipartiteness 二分图的最大匹配问题-白红宇

Codeforces 435 B Mahmoud and Ehab and the bipartiteness 二分图的最大匹配问题

阅读量：6166 次

发布时间：2019-06-21

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

　　题目链接： http://codeforces.com/contest/862/problem/B

　　题目描述：给一个图，问最多连多少线，可以作为二分图

　　解题思路：求二分图的最大匹配， DFS

　　代码：

#include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;typedef long long ll;const int maxn = 1e5+10;int n;int color[maxn];vector
             
               G[maxn];void dfs( int s, int co ) { color[s] = co; for( int i = 0; i < (int)G[s].size(); i++ ) { int to = G[s][i]; if( color[to] == 0 ) { dfs(to, -1*co); } }}int main() { scanf( "%d", &n ); for( int i = 0; i < n-1; i++ ) { int u, v; scanf( "%d%d", &u, &v ); G[u].push_back(v); G[v].push_back(u); } int s1 = 0; dfs(1, 1); for( int i = 1; i <= n; i++ ) { if( color[i] == -1 ) s1++; } printf( "%lld\n", 1ll*(n-s1)*s1-1ll*n+1ll); return 0;}