CodeForces 1263D Secret Passwords 并查集

[题目大意]
输入若干个密码（字符串），如果两个字符串含有相同的字母，则可以使用其中任意一个密码解开它们（即属于同一集合中），很明显用并查集解题即可。
这里用vector存取分别含有每个字母的单词，然后进行并查集操作即可。

[样例]
Input
4
a
b
ab
d

Output
2

Input
3
ab
bc
abc

Output
1

Input
1
codeforces

Output
1

AC代码

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
const int maxn=200005;
using namespace std;
int vec[26][maxn]={0};
int p[maxn];
int find(int x)
{return p[x]==x ? x:p[x]=find(p[x]);
}//并查集 
void unity(int x,int y)
{int s=find(x);int t=find(y);p[s]=t;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n,ans=0;string s;cin>>n;for(int i=1;i<=n;i++)p[i]=i;//并查集初始化 for(int i=1;i<=n;i++){cin>>s;int len=s.length();for(int j=0;j<len;j++)vec[s[j]-'a'][i]=1;}//从1到n分别表示字符串的编号 for(int i=0;i<26;i++){int x,y,pos=-1;for(int j=1;j<=n;j++){if(vec[i][j]==1){pos=j;x=find(j);//这里在后面没有及时更新，要注意细节 break;}}if(pos==-1) continue;for(int j=pos+1;j<=n;j++){if(vec[i][j]==1){y=find(j);unity(x,y);}}}for(int i=1;i<=n;i++){if(i==find(i))ans++;}cout<<ans<<endl;return 0;
}

当时ACM周赛我很快通过了这道题，要感谢过去半年以来的积累，接触到了很多新的知识。依靠罚时少的优势，我第一次拿到了周赛的第一名。大学以前我并没有接触过编程，这是我过去都不敢想象的。所以所有的事情都可以通过自己的努力一步一步去实现，只要你坚持不放弃。
我想铭记每一个这样的瞬间，让我能够回顾自己的心路历程，真的要感谢自己能够从零基础的纯小白走到现在，也曾历经过挫折但未曾放弃，有时为了题目当中的一些细节，我可以花好几个小时查资料调试，甚至通宵到第二天都没有睡觉。前路漫漫，也许会经历更多未知的艰难的考验，我想，不求尽如人意，但求无愧于心。
每天坚持训练，也许更多的是一种情怀吧。若将来有一天，我能够站到ACM比赛的舞台上，一定也会是那样的感受吧。“也许很累一身狼狈，也许卑微一生无为，谁生来不都是一样，尽管叫我无名之辈”。相信黎明的那道光，终会越过黑暗，暴风雨的尽头会是彩虹！