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
#include
#include
#include
#include
using namespace std;
const int MAXN=11111;//根据点的个数变
int linker[MAXN];
bool used[MAXN];
vectormap[MAXN];
int uN;
bool dfs(int u)
{
for(int i=0;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
{
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
map[i].clear();
for(i=0;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
#include
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
{
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;
}