西电1228 最大匹配 二分匹配求最大的组数
http://acm.xidian.edu.cn/land/problem/detail?problem_id=1228&contest_id=22
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个人）
问最多能组成多少个组

#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])]++;        }        for(i=1;i<=n;i++)        {            s=s+ss[i]/2;        }        printf("%d\n",s);    }    return 0;}