Problem 10608 Friends，最大朋友群

鎮上有 N 個人，照一句諺語說：「我朋友們的朋友也是我的朋友」。A 和 B 為朋友，B 和 C 為朋友，所以 C 和 A 也為朋友。

讀入 N 和 M 兩整數，N 為鎮上有公民 1 - N，而接下來會有 M 列資料，M 列資料都有兩整數 a, b，代表公民 a 和公民 b 為朋友。最後請你算出這鎮上最大朋友群的數量為多少。

其實只要給朋友群定義一個朋友群編號，如果雙方都沒有朋友群編號，就將兩人都定義一個新的朋友群編號，並將此朋友編號數量變成 2；若兩人其中一人沒有朋友群編號，則將他加入有編號的朋友群之中；如果兩人都有朋友群編號，就將其中一方的所有朋友的編號改為另一方的編號，順便將另一方朋友編號數量累加對方的數量。

一開始宣告陣列以及初始化朋友群編號以及朋友群數量：

scanf("%d %d", &n, &m);
int friends[n + 1], record[n + 1], max = 0;
count = 0, groupID = 1;
memset(friends, 0, sizeof(friends));
memset(record, 0, sizeof(record));

接下來用以上敘述的概念寫成分群並且計算數量的方法，順便記錄最大值，寫成 C 語言程式碼如下：

while (m --)
{
    scanf("%d %d", &a, &b);
    if (friends[a] == 0 && friends[b] == 0)
    {
        friends[a] = groupID, friends[b] = groupID;
        record[groupID] = 2;
        if (max < record[groupID]) max = record[groupID];
        
        groupID ++;
        count ++;
    }
    else if((friends[a] != 0 && friends[b] == 0) ||
            (friends[a] == 0 && friends[b] != 0))
    {
        tmp = friends[a] < friends[b] ? friends[b] : friends[a];
        friends[a] = tmp, friends[b] = tmp;
        record[tmp] ++;
        if (max < record[tmp]) max = record[tmp];
    } 
    else if (friends[a] != friends[b])
    {
        tmp = friends[b];
        replace = friends[a];
        record[tmp] = 0;
        for (s = 1; s <= n; s ++)
            if (friends[s] == tmp) friends[s] = replace, record[replace] ++;
        if (max < record[replace]) max = record[replace];
        count --;
    }
    /* for (s = 1; s <= n; s ++)
        printf("%d ", record[s]);
    printf("\n"); */
}
printf("%d\n", max);

By David.K

p10608題目連結
回ACM題庫目錄
回首頁