louisfghbvc的部落格

題目連結:  https://onlinejudge.org/external/115/11503.pdf

題目大意:  朋友的朋友也是朋友

思路: 單純的並查集，記得紀錄集合大小即可，還要注意是不是已經在同個集合裡。同個集合不合併。

這邊用了小技巧，將群組值大小變成負的，並且只有樹根才有群組值，省記憶體。

代碼:  

#include <bits/stdc++.h>
#define N 100005
using namespace std;

int p[N];
int findp(int x){
    return p[x] < 0 ? x : p[x] = findp(p[x]);
}

int main()
{
    //freopen("out.txt", "w", stdout);
    int t, q;
    string a, b;
    cin >> t;
    while(t--){
        memset(p, -1, sizeof p);
        cin >> q;
        map<string, int> mp;
        while(q--){
            cin >> a >> b;
            if(!mp.count(a)) mp[a] = mp.size();
            if(!mp.count(b)) mp[b] = mp.size();
            int ap = findp(mp[a]), bp = findp(mp[b]);
            if(ap != bp){
                p[ap] += p[bp];
                p[bp] = ap;
            }
            cout << abs(p[ap]) << endl;
        }
    }
    return 0;
}
/**
1
3
Fred Barney
Barney Betty
Betty Wilma
**/