#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
- （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 ...
- 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 ( ...
- 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 ( ...
- 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 ...
- 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 ...
- 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 ( ...
- 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 ...
- 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 ...
- 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
- Mysql5.0 following Manual injection
order by 20 www. .com/product/introduction.php?id=-65 UNION SELECT user(),2 www. .com/product/introd ...
- 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 ...
- 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 ...
- flutter Read sdcard It's about access
https://stackoverflow.com/questions/46698751/permission-denied-at-externalstoragedirectory-access-vi ...
- 【leetcode】485. Max Consecutive Ones
problem 485. Max Consecutive Ones solution1: class Solution { public: int findMaxConsecutiveOnes(vec ...
- 【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 , ...
- 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 ...
- 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 ...
- 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 ...
- 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