Secret Passwords（二分图）

薇点18666053854One unknown hacker wants to get the admin's password of AtForces testing system, to get problems from the next contest. To achieve that, he sneaked into the administrator's office and stole a piece of paper with a list of nn passwords — strings, consists of small Latin letters.

Hacker went home and started preparing to hack AtForces. He found that the system contains only passwords from the stolen list and that the system determines the equivalence of the passwords aa and bb as follows:

two passwords aa and bb are equivalent if there is a letter, that exists in both aa and bb; two passwords aa and bb are equivalent if there is a password cc from the list, which is equivalent to both aa and bb. If a password is set in the system and an equivalent one is applied to access the system, then the user is accessed into the system.

For example, if the list contain passwords "a", "b", "ab", "d", then passwords "a", "b", "ab" are equivalent to each other, but the password "d" is not equivalent to any other password from list. In other words, if:

admin's password is "b", then you can access to system by using any of this passwords: "a", "b", "ab"; admin's password is "d", then you can access to system by using only "d". Only one password from the list is the admin's password from the testing system. Help hacker to calculate the minimal number of passwords, required to guaranteed access to the system. Keep in mind that the hacker does not know which password is set in the system.

Input

The first line contain integer nn (1≤n≤2⋅1051≤n≤2⋅105) — number of passwords in the list. Next nn lines contains passwords from the list – non-empty strings sisi, with length at most 5050 letters. Some of the passwords may be equal.

It is guaranteed that the total length of all passwords does not exceed 106106 letters. All of them consist only of lowercase Latin letters.

Output

In a single line print the minimal number of passwords, the use of which will allow guaranteed to access the system.

Examples

input

Copy

4 a b ab d output

Copy

2 input

Copy

3 ab bc abc output

Copy

1 input

Copy

1 codeforces output

Copy

1 Note

In the second example hacker need to use any of the passwords to access the system.

题意：第一行给定一个数n，接下来n行，每行一串字符，代表一种可能的密码，通过将所有可能的密码都试一遍来获取正确密码，因为其中有等价的密码，因此一组等价的密码只需要输入其中一个（输入这一个就相当于把这一组等价的密码都试了一遍），问：将所有的可能的密码试一遍需要最少输入的密码个数（即：等价密码的组数）。

密码视为等价的两种情况是：1、两个串中有相同字符；2、两个串组合起来构成第三个串，并且这三个串都在可能的密码集合里，那就将这三个串视为等价。

思路：下面用二分图解决，用vector g[maxn]存图，g[i]表示编号为i的串含有的字符的集合或编号为i的字符对应的串的集合，即：在每个串和其中的字符之间建一条边，然后根据密码等价的定义，显然答案即为二分图中连通分量的个数（一个连通分量即代表一组等价的密码的编号和其中对应的边的集合）。

完整代码：

#include <bits/stdc++.h> #define int long long using namespace std; const int maxn=2e5+26;//注意最后遍历26个字符对应的编号时，最大的为n+25，因此数组范围要到2e5+26 int n,vis[maxn]; string s; vector g[maxn];

void addEdge(int u,int v) { g[u].push_back(v); g[v].push_back(u); }

void dfs(int u) { vis[u]=1; for(int i=0;i<g[u].size();i++)//遍历编号为u的串含有的字符集合或遍历编号为u的字符对应的串的集合 { int id=g[u][i]; if(!vis[id]){ dfs(id); } } }

signed main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n; for(int i=0;i<n;i++) { cin>>s; for(int j=0;j<s.size();j++) { addEdge(i,n+s[j]-'a');//i为该串s的编号，通过n+s[j]-'a'来得到s[j]这个字符对应的编号 } } int ans=0; for(int i=n;i<n+26;i++)//遍历每个字符对应的编号(n<==>a,n+1<==>b...) { if(!g[i].empty()&&!vis[i]) { dfs(i);//当找不到新的未标记的编号(即遍历完了一组等价密码（即：找到了一个连通分量)）时dfs退出 ans++;//此时,等价密码组数+1 } } cout<<ans<<endl; return 0;

———————————————— 版权声明：本文为CSDN博主「Mr_Kingk」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/Mr_Kingk/article/details/103337508