Secret Passwords
A. Secret Passwords
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
One 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 n 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 a and b as follows:
two passwords a and b are equivalent if there is a letter, that exists in both a and b;
two passwords a and b are equivalent if there is a password c from the list, which is equivalent to both a and b.
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 n (1≤n≤2⋅105) — number of passwords in the list. Next n lines contains passwords from the list – non-empty strings si, with length at most 50 letters. Some of the passwords may be equal.
It is guaranteed that the total length of all passwords does not exceed 106 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
inputCopy
4
a
b
ab
d
outputCopy
2
inputCopy
3
ab
bc
abc
outputCopy
1
inputCopy
1
codeforces
outputCopy
1
Note
In the second example hacker need to use any of the passwords to access the system.
这是一道简单的并查集问题，想做下来必须掌握“并查集”基本概念，并熟悉的转化为代码。
大家可以看一下这位大牛对并查集的理解；
java的api文档是个好东西；菜鸡java永远不用像C的大佬一样很快打出基本算法；
并查集详解
接下来的代码我也将利用大牛的思路来分析代码。故事是这样的：
江湖上有26个武功高强的大侠，我们并不清楚他们属于什么门派。
现在假设天下有26门派；
现在我们给出n张大侠照片，如果照片上同时出现了几位大侠，我们认为大侠属于同一个派别；
比如：asd,bsh,nm,
那么我们可以肯定：asdbsh六位大侠属于一派（可能武当派），mn两位是一派（可能是峨眉派）；
我们假设DSU是一个照片，数组p代表大侠，而数组的值代表大侠所属门派，我们假定大侠最初都是自立门派。
如果p[i]==i，我们认为大侠属于自己门派，p[i]==j,则属于大侠j;
import java.util.Scanner;
public class SecretPasswords {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
//大侠的照片数量（字符串数目）
int n=sc.nextInt();
//temp暂时保存大侠的照片，并分析里面都有谁
String temp;
//flag 标记大侠是否在该照片出现过，total用来确定所有照片上出现的大侠
boolean[] total=new boolean[26],flag ;
DSU obj=new DSU();
while(n-->0) {
temp=sc.next();
flag=new boolean[26];
//for的一种简单写法等价于:
//for(int i=0;i<temp.toCharArray().length;i++){
// flag[temp.charAt(i)-'a']=true;
// }
//大侠若出现标记为true
for(char c:temp.toCharArray()) {
flag[c-'a']=true;
}
//如果一张照片上出现了该大侠，total记录大侠出现过
//obj.union来对大侠门派做判断
for(int i=0;i<26;i++) {
if(flag[i]) {
total[i]=true;
obj.union(temp.charAt(0)-'a',i);
}
}
}
sc.close();
//如果大侠出现过，我们才能判断他的派别，否则默认自称门派，我们不统计没有出现过的大侠
//如果数组p[i]==i，则代表属于一派，p[j]==i,，则大侠j隶属于大侠i,不需要记录大侠j的门派
int count =0;
for (int i = 0; i < 26; i++) {
if(total[i]&&obj.getParent(i)==i) {
count++;
}
}
System.out.println(count);
}
}
class DSU{
int[] p;
DSU(){
p=new int[26];
for(int i=0;i<26;i++) {
p[i]=i;//默认大侠自立门派
}
}
int getParent(int i) {
if(p[i]==i) {//如果大侠自立门派，执行if语句，否子执行下一句，查找大侠门派，并修改p[i],便于确认大侠门派
return i;即可能大侠a属于大侠b,大侠b属于大侠c,大侠c属于大侠d;这样太麻烦，我们直接改为大侠a属于大侠d;
}
return p[i]=getParent(p[i]);
}
void union (int i,int j) {//如果在一张照片上出现了大侠i，大侠j,那么大侠i,j属于同一门派
i=getParent(i);
j=getParent(j);
if(i!=j) {
p[j]=getParent(i);
}
}
}
故事编完了，代码写完了，菜鸡的我还得多多练习！