C++14(g++5.4) 解法, 执行用时: 385ms, 内存消耗: 1624K, 提交时间: 2020-01-05 16:29:37

#include<bits/stdc++.h>
using namespace std;
int f[10];
int t[10];
int Find(int x){
	if(x==f[x]) return f[x];
	else return Find(f[x]);
}
int Combine(int a,int b){
	int fa=Find(a);
	int fb=Find(b);
	if(fa!=fb)
	f[fa]=fb;
}
int main(){
	int cas;
	cin >> cas;
	while(cas--){
		for(int i=0;i<=9;i++){
			f[i] = i;
			t[i] = 0;
		} 
		int n;
		cin >> n;
		while(n--){
			string s;
			cin >> s;
			t[s[0]-'0']=1;
			for(int i=1;i<s.size();i++){
				t[s[i]-'0']=1;
				Combine(s[0]-'0',s[i]-'0');
			}
		}
		int cnt = 0;
		for(int i=0;i<=9;i++){
			if(t[i]){
				if(Find(i)==i)
				cnt++;
			}
		}
		cout << cnt << endl;
	}
	return 0;
}

Python3(3.5.2) 解法, 执行用时: 247ms, 内存消耗: 8400K, 提交时间: 2020-01-05 15:33:29

T = int(input())

while T:
    T -= 1
    n = int(input())
    items = []
    for _ in range(n):
        cur = set(input())
        if not items:
            items.append(cur)
        else:
            union = []
            for i in range(len(items)):
                if items[i] & cur:
                    union.append(i)
            if not union:
                items.append(cur)
            else:
                union.reverse()
                for i in union:
                    cur |= items[i]
                    items.remove(items[i])
                items.append(cur)
    print(len(items))

C++(clang++ 11.0.1) 解法, 执行用时: 131ms, 内存消耗: 412K, 提交时间: 2023-01-30 16:18:06

#include<bits/stdc++.h>
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
int vis[10],qaq[10];
int find(int x){ return vis[x]==x?x:find(vis[x]); }
int main(){
	int _; cin>>_; while(_--){
		rep(i,0,10) qaq[i]=0,vis[i]=i;
		int n,cnt(0); cin>>n; while(n--){
			string s; cin>>s; int len=s.length(); qaq[s[0]-'0']=1;
			rep(i,1,len) vis[find(s[i]-'0')]=find(s[0]-'0'),qaq[s[i]-'0']=1;
		} rep(i,0,10) if(qaq[i]&&vis[i]==i) cnt++; cout<<cnt<<'\n';
	}
}