西电1228 最大匹配二分匹配求最大的组数

Problem 1228 - 最大匹配
Time Limit: 1000MS   Memory Limit: 65536KB  Difficulty:
Total Submit: 220  Accepted: 31  Special Judge: No
Description
有N个人手牵着手（当然可能有的人没有跟其他任何人牵手），现在需要将他们分组，只有直接牵着手的两个人才有可能分到一组，问最多能分多少组？ps:因为每个人只有两只手，最多只能牵两个人
Input
有多组数据
每组第一行为两个正整数N,M，表示N个人，M个牵手关系。（1<=N,M<=10000）
接下来M行每行两个正整数a，b表示a，b两个牵着手(1<=a,b<=n，a!=b，保证a,b不会重复)
Output
对于每组数据，输出一行，一个正整数即最大能分配的组数
Sample Input
3 3
1 2
2 3
1 3
Sample Output
1
Hint
Source
cyin
 
题意： 输入n m  n个点 m个对
输入m个对  每对表示 a b 可以为一组     （一组只能有2个人，而且1个人不能在2个组中  只有2个人才能组成一个组  。一个人只有2只手  只能牵2个人）
问最多能组成多少个组
 
 
 
 
 
思路 ：
 
 
 
二分匹配
 
 
 
[cpp]  
#include<stdio.h>  
#include<iostream>  
#include<algorithm>  
#include<string.h>  
#include<vector>  
using namespace std;  
const int MAXN=11111;//根据点的个数变  
int linker[MAXN];  
bool used[MAXN];  
vector<int>map[MAXN];  
int uN;  
bool dfs(int u)  
{      
    for(int i=0;i<map[u].size();i++)          
    {          
        if(!used[map[u][i]])              
        {              
            used[map[u][i]]=true;              
            if(linker[map[u][i]]==-1||dfs(linker[map[u][i]]))                  
            {                  
                linker[map[u][i]]=u;                  
                return true;              
            }              
        }          
    }      
    return false;      
}  
int hungary()  
{      
    int u;      
    int res=0;      
    memset(linker,-1,sizeof(linker));      
    for(u=0;u<uN;u++)          
    {          
        memset(used,false,sizeof(used));          
        if(dfs(u)) res++;          
    }      
    return res;      
}  
int main()  
{  
    int u,k,v,i;      
    int n,m;      
    while(scanf("%d %d",&n,&m)!=EOF)          
    {          
        for( i=0;i<MAXN;i++)              
            map[i].clear();  
        for(i=0;i<m;i++)  
        {  
            scanf("%d %d",&v,&u);     
            v=v-1;//如果点是从1开始计数的 要减1  如果从0开始去掉这句以及下面那句  
            u=u-1;  
            map[u].push_back(v);          
            map[v].push_back(u);      
        }  
        uN=n;      
        printf("%d\n",hungary()/2);      
    }      
    return 0;      
}  
 
 
 
 
 
      由于只能牵2个人的手 那么可以用并查集做
      每个人只能只有一个父亲节点 且只有一个儿子节点   那么能牵手的人组成了一条线
     那么这个线上的人 每2个成为一组  线上人数除以2   加上所有线上的结果就是答案
 
[cpp]  
#include <stdio.h>  
#include <string.h>  
int ss[10022];  
int a[10022];  
int f(int x)  
{  
    while(x!=a[x])  
        x=a[x];  
    return a[x];  
}  
int main()  
{  
    int i,j,m,n;  
    int x1,x2;  
    while(scanf("%d%d",&n,&m)!=EOF)  
    {  
        for(i=1;i<=n;i++)  
        {  
            a[i]=i;  
            ss[i]=0;  
        }  
        memset(ss,0,sizeof(ss));  
        while(m--)  
        {  
            scanf("%d%d",&x1,&x2);  
            x1=f(x1);  
            x2=f(x2);  
            if(x1<x2)  
            {  
                a[x2]=x1;  
            }  
            else  
                a[x1]=x2;  
        }  
        int s=0;  
        for(i=1;i<=n;i++)  
        {  
            ss[f(a[i])]++;  
  &n

补充：软件开发 , C++ ,

西电1228 最大匹配 二分匹配求最大的组数

西电1228 最大匹配二分匹配求最大的组数