这道题首先判断一下图是不是二部图,如果是的话,就进行二分匹配
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 300; int n, m; int color[N]; int g[N][N], linker[N]; bool used[N]; bool dfs( int u ) { int i; for ( i = 1; i <= n; ++i ) if ( g[u][i] ) { if ( !used[i] ) { used[i] = true; if ( linker[i] == -1 || dfs(linker[i]) ) { linker[i] = u; return true; } } } return false; } int match() { int res = 0; memset( linker, -1, sizeof(linker)); for ( int u = 1; u <= n; ++u ) { memset( used, 0, sizeof(used) ); if ( dfs( u ) ) res++; } return res; } bool bipartite( int x ) { for ( int i = 1; i <= n; ++i ) { if ( g[x][i] && color[i] == color[x] ) return false; if ( g[x][i] && !color[i] ) { color[i] = 3-color[x]; if ( !bipartite(i) ) return false; } } return true; } int main() { while ( scanf("%d%d", &n, &m) == 2 ) { memset( g, 0, sizeof(g)); memset( color, 0, sizeof(color)); for ( int i = 1; i <= m; ++i ) { int u, v; scanf("%d%d", &u, &v); g[u][v] = g[v][u] = 1; } color[1] = 1; if ( !bipartite(1) ) { printf("No\n"); continue; } printf("%d\n", match()/2); } }