UVa11503 - Virtual Friends(Disjoint Set)

題目大意：

大家都喜歡線上交友，線上交友成為了一種大家的習慣或嗜好，我們每行會給你兩個名子，那兩個人是朋友關係，因為線上交友的關係，因此那兩人的朋友們也都會互相成為朋友。

每次新增朋友關係後，請試者輸出那群朋友的數量

題目連結

重點觀念

• 了解 Disjoint Set
• 演算法知識 - Disjoint Set 並查集

分析：

很明顯的並查集，我們只需要寫好並查集的模板，接著將字串進行 hash，就可以得到答案。

心得

最近這幾天心情很煩燥，很多事情都安不下心，我還是一個小孩，還不願成長為一個大人，好多事情我都想逃避，但是世界不會讓我逃避、都市不會讓我逃避。

希望最近能讓我好點。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

裡面為了讓程式碼更好寫，有做一些小手腳，在這邊會加上一些定義，供大家在閱讀時更好閱讀

• num 為 disjoint set 判斷 num[index] 在哪個集合內
• cnt 為 disjoint set 判斷 cnt[index] 此代表元素的集合內有多少元素有多少元素
• hs 用來 hash 值，來讓字串進行加密壓縮
• record 字典，用來紀錄字串 hash 成 int 的值

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 100020
using namespace std;
int t, f, hs;
int num[MAXN], cnt[MAXN]; 
string n1, n2;
unordered_map<string, int> record;

int find_root(int i){ //disjoint set 查詢
    if(num[i] != i) return num[i] = find_root(num[i]);
    return num[i];
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin >> t;
    for(int i = 0; i < MAXN; i++){ //最一開始先幫所有陣列初始化
        num[i] = i; //重設 disjoint set
        cnt[i] = 1; //重設 disjoint set
    }
    while(t--){
        cin >> f;
        hs = 0; record.clear();
        for(int i = 0; i < f; i++){ //讓上次測資不干擾這次測資
            num[i] = i;  //重設 disjoint set
            cnt[i] = 1;  //重設 disjoint set
        }
        for(int i = 0; i < f; i++){
            cin >> n1 >> n2;
            //壓縮字串為 int，如果字典沒有這個字串那就給他從未用過的 hash 值
            if(!record.count(n1)) record[n1] = hs++; 
            if(!record.count(n2)) record[n2] = hs++;
            int rx, ry;
            //為 disjoint set 的合併，開始
            rx = find_root(num[record[n1]]); 
            ry = find_root(num[record[n2]]); 
            if(rx != ry){ 
                num[ry] = num[rx];
                cnt[rx] += cnt[ry];
                cnt[ry] = 0;
            }
            //為 disjoint set 的合併，結束
            cout << cnt[rx] << '\n'; //輸出集合內的元素數量
        }
    }
    return 0;
}