【TOJ 3955】NKU ACM足球賽（加權並查集）

描述

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