【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; }