【題解】ZeroJudge b839: 104北二3.朋友

#include <iostream>
using namespace std;

int t, n, p[55], mx;
string s[55];

int pa(int x){
    if (p[x] < 0) return x;
    else return p[x] = pa(p[x]);
}
bool check(string a, string b){
    int dp[55][55] = {};
    for (int i = 1; i <= a.length(); i++){
        for (int j = 1; j <= b.length(); j++){
            if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1]+1;
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    if (dp[a.length()][b.length()] >= (min(a.length(), b.length())+1)/2) return true;
    return false;
}

int main() {
    cin >> t;
    while (t--){
        cin >> n;
        mx = 1;
        for (int i = 1; i <= n; i++){
            cin >> s[i];
            p[i] = -1;
            for (int j = 1; j < i; j++){
                int a = pa(i), b = pa(j);
                if (a != b && check(s[i], s[j])){
                    p[a] += p[b];
                    mx = max(mx, -p[a]);
                    p[b] = a;
                }
            }
        }
        cout << mx << "\n";
    }
}