当前位置:新注册送38元体验金 > 新注册送38元体验金编程 > 【TOJ 3955】NKU ACM足球赛(加权并查集),tojnku

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

文章作者:新注册送38元体验金编程 上传时间:2019-08-22

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

描述

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("%dn",s);
    }
    return 0;
}

3955】NKU ACM足球赛(加权并查集),tojnku 描述 NKU ACM最近要举行足球赛,作为此次赛事的负责人,Lee要对报名人员进行分队。分队要遵...

本文由新注册送38元体验金发布于新注册送38元体验金编程,转载请注明出处:【TOJ 3955】NKU ACM足球赛(加权并查集),tojnku

关键词: