欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【TOJ 3955】NKU ACM足球赛(加权并查集)

程序员文章站 2022-03-27 21:04:47
描述 NKU ACM最近要举行足球赛,作为此次赛事的负责人,Lee要对报名人员进行分队。分队要遵循如下原则: 一个人不能加入多支队伍;不认识的人不能分在同一队;如果a和b认识,b和c认识,那么认为a和c也认识;每支队伍上限8人,下限5人;尽量使队伍满员。由于参赛人数很多,Lee表示无能为力,所以请你 ......

描述

NKU ACM最近要举行足球赛,作为此次赛事的负责人,Lee要对报名人员进行分队。分队要遵循如下原则:

一个人不能加入多支队伍;
不认识的人不能分在同一队;
如果a和b认识,b和c认识,那么认为a和c也认识;
每支队伍上限8人,下限5人;
尽量使队伍满员。
由于参赛人数很多,Lee表示无能为力,所以请你帮助Lee编程解决比赛有多少队伍。

输入

第一行输入两个整数,n和m,n(1<=n<=300000)代表报名人数,m(1<=m<=500000)代表关系数。接下来m行每行两个整数a(1<=a<=n)和b(1<=b<=n)表示a和b认识。

输出

输出一行,包含一个整数,表示队伍数量。

样例输入

11 10
1 2
2 3
2 6
3 4
4 5
5 6
7 9
9 11
11 8
8 10

样例输出

 2

#include<iostream>
#include<algorithm>
using namespace std;
int p[300005],rank[300005]; 
int find(int r)
{
    if(p[r]!=r)
    p[r]=find(p[r]);
    return p[r];
}
int join(int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fx!=fy)
    {
        p[fx]=fy;
        rank[fy]+=rank[fx];
        rank[fx]=1;                      //把加过的秩数组变为1
    }
}
int main()  
{  
    int n,m,a,b,s;
    while(cin>>n>>m)
    {
        s=0;
        for(int i=0;i<=300005;i++)
            p[i]=i,rank[i]=1;
        while(m--)
        {
            scanf("%d%d",&a,&b);
            join(a,b);
        }
        for(int i=1;i<=n;i++)
        {
            if(rank[i]>=5)
            {
                if(rank[i]%8>=5)
                    s+=rank[i]/8+1; 
                else 
                    s+=rank[i]/8;
            }
        }
        printf("%d\n",s);
    }
    return 0;
}