#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define maxn 210
int map[maxn][maxn],color[maxn];
int vis[maxn],match[maxn],n;
int bfs(int u,int n)
{
int i;
queue<int>q;
q.push(u);
color[u]=;
while(!q.empty())
{
int v=q.front();
q.pop();
for(i=;i<=n;i++)
{
if(color[i]==-&&map[v][i])
{
q.push(i);
color[i]=!color[v];
}
if(color[i]==color[v]&&map[v][i])
return ;
}
}
return ;
}
int dfs(int u)
{
int i,j;
for(i=;i<=n;i++)
{
if(map[u][i]&&!vis[i])
{
vis[i]=;
if(match[i]==-||dfs(match[i]))
{
match[i]=u;
return ;
}
}
}
return ;
}
int main()
{
int i,j,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(color,-,sizeof(color));
memset(map,,sizeof(map));
memset(match,-,sizeof(match));
for(i=;i<m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
map[x][y]=map[y][x]=;
}
int flag=;
for(i=;i<=n;i++)
{
if(color[i]==-&&!bfs(i,n))
{
flag=;
break;
}
}
if(!flag)
{
printf("No\n");
continue;
}
int ans=;
for(i=;i<=n;i++)
{
memset(vis,,sizeof(vis));
if(dfs(i))
ans++;
}
printf("%d\n",ans/);
}
}

hdu2444 Judge bipartite graph + More related articles on maximum matching

  1. (hdu)2444 The Accomodation of Students Judge bipartite graph + The maximum number of matches

    Topic link :http://acm.split.hdu.edu.cn/showproblem.php?pid=2444 Problem Description There are a group of s ...

  2. hdu 2444( To judge a bipartite graph by coloring + The biggest match )

    The Accomodation of Students Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K ( ...

  3. HDU 2444 The Accomodation of Students( Judge bipartite graph + The biggest match )

    The Accomodation of Students Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K ( ...

  4. hdu 2444 Bipartite graph judgment and maximum matching

    The question : Yes n A student , Yes m I know people , Each pair of people they know can be assigned a room , Ask if you can put n The students are divided into two parts , The students in each part don't know each other , And the students between the two parts know . If it can be divided into two parts , Even if you need to get out of the room at most , Otherwise output No ...

  5. hdu2444( Judge bipartite graph + The biggest match )

    Portal :The Accomodation of Students The question : Yes n A student ,m To know each other , Can we split into two teams , So that there is no mutual understanding in each pair , If we can get the maximum match , Otherwise output No. analysis : Judge a bipartite graph by coloring ...

  6. HDU2444(KB10-B Bipartite graph decision + The biggest match )

    The Accomodation of Students Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K ( ...

  7. Luogu 1402 The king of hotels ( Maximum matching of bipartite graph )

    Luogu 1402 The king of hotels ( Maximum matching of bipartite graph ) Description XX The owner of the hotel wants to be the king of the hotel , In this hope , The first step is to humanize the hotel . As many visitors to the hotel have their own favorite room colors . Sunshine, etc , It's also self-evident ...

  8. Luogu 2756 Pilot pairing problem ( Maximum matching of bipartite graph )

    Luogu 2756 Pilot pairing problem ( Maximum matching of bipartite graph ) Description The RAF recruited a large number of foreign pilots from the occupied countries . Every aircraft sent by the Royal Air Force needs to be equipped with a combination of navigation skills and language 2 Mingfei ...

  9. Luogu 1559 Athletes' best match problem ( Maximum matching of weighted bipartite graphs )

    Luogu 1559 Athletes' best match problem ( Maximum matching of weighted bipartite graphs ) Description There are male and female players in the badminton team n people . Given 2 individual n×n matrix P and Q.P[i][j] It's a male athlete i And female athletes j Pairing makes mixed doubles ...

Random recommendation

  1. Mysql5.0 following Manual injection

    order by 20 www. .com/product/introduction.php?id=-65 UNION SELECT user(),2 www. .com/product/introd ...

  2. C# Generic 2

    When we write the program , We often encounter that the functions of two modules are very similar , Just one is dealing with int data , The other is to deal with string data , Or other custom data types , But we have no way , You can only write multiple methods to handle each data type , Because the parameter class of the method ...

  3. PS Filter —— Sketch algorithm ( Two )

    Another algorithm is used to generate sketch effects . %%% Sketch clc; clear all; Image=imread('4.jpg'); Image=double(Image); [row,col,l ...

  4. flutter Read sdcard It's about access

    https://stackoverflow.com/questions/46698751/permission-denied-at-externalstoragedirectory-access-vi ...

  5. 【leetcode】485. Max Consecutive Ones

    problem 485. Max Consecutive Ones solution1: class Solution { public: int findMaxConsecutiveOnes(vec ...

  6. 【JavaScript From entry to mastery 】 The third class On JavaScript charm -03

    The third class On JavaScript charm -03 Function arguments Last time we talked about functions , actually , Functions are similar in function to css Of class equally , Wrap up a piece of code to use . In order to make the function more rich and practical , ...

  7. spring boot Series five :spring boot adopt devtools Hot deployment

    I've shared four essays before : spring boot One of series :spring boot introduction spring boot The second series :spring boot How to modify the default port number and contextpath spri ...

  8. change color3

    The two methods The first one is DataGridview1.Rows[i].DefultCellStyle.backcolor The second kind AlternatingRowsDefutCellstyle attribute Gets or sets the value that should be ...

  9. 20145206 Zou Jingru Exp8 Web Basics

    20145206 Zou Jingru Exp8 Web Basics One . Practice process record Apache ( One ) Environment configuration 1. Check port usage : ad locum apach2 Occupied port 80 2. test apache Whether it works properly : stay kali On the Internet ...

  10. Vcenter The method of migrating four network cards of server from port group to distributed switch at one time

    If your server is already on the list , Then you can delete this server from the distributed switch first , And then add it again . At this time, you can select four network cards ( Including port groups , Including management port groups ), Join the distributed switch at one time