D. Secret Passwords_并查集

D. Secret Passwords

题目大意

给一堆字符串，两个串有一个字母一样就算等效。问所有字符串里有几个不等效的。

思路

并查集入门题

ll fa[N] ;

ll find(ll x){
	return fa[x] = fa[x] == x ? x : find(fa[x]) ;
}

void solve(){
	ll n ; cin >> n ;
	ll ans = n ;
	
	vct<vct<ll> > letter(40) ; 
	
	rep(i , 1 , n) fa[i] = i ;
	
	rep(i , 1 , n){
		string s ;
		cin >> s ;
		for (char c : s) letter[c - 'a'].pb(i) ;
	}
	
	rep(i , 0 , 30){
		if(letter[i].size() < 2) continue ;
	
		ll ft = find(letter[i][0]) ;
		rep(j , 1 , letter[i].size() - 1){
			ll fi = find(letter[i][j]) ;
			if(ft != fi){
				ans -- ;
				fa[fi] = ft ;
			}
		}
	}
	
	cout << ans << "\n" ;
}//code_by_tyrii