ll T; while(~scanf("%d",&T)){ while(T--) {
= = ...
思路：
用秩合并，看了题解才发现 if(fx == fy)要输出当前集合的秩而不是0。。。
#include #include #include #include #include #include #include #include #include #include using namespace std; #define mod 1000000007 #define ll int #define N 100100 ll r[N], f[N]; ll find(ll x){return x==f[x]?x:f[x] = find(f[x]);} ll Union(ll x, ll y){ ll fx = find(x), fy = find(y); if(fx==fy)return r[fx]; if(r[fx]>r[fy]) swap(fx,fy); f[fx] = fy; r[fy] += r[fx]; return r[fy]; } ll n; void init(){ for(ll i = 0; i < N; i++) r[i] = 1; for(ll i = 0; i < N; i++) f[i] = i; } #define Word_Len 50500 #define Sigma_size 95 struct Trie{ ll ch[Word_Len][Sigma_size]; //Word_Len是字典树的节点数 若都是小写字母Sigma_size=26 ll Have_word[Word_Len]; //这个节点下有几个单词 ll val[Word_Len]; // 这个节点附带的信息，初始化为0表示这个节点不存在单词，所以节点带的信息必须!=0 ll sz ; //当前节点数 ll pre[Word_Len]; char he[Word_Len]; ll Newnode(){memset(ch[sz], 0, sizeof(ch[sz])); val[sz]=Have_word[sz]=0; return sz++;} void init() //初始化字典树 { sz = 0; Newnode();}//初始化 ll idx(char c){return c-32;} //字符串编号 ll insert(char *s){ //把v数字加给 s单词最后一个字母 ll u = 0, len = strlen(s); for(ll i = 0; i < len; i++){ ll c = idx(s[i]); if(!ch[u][c]) //节点不存在就新建后附加 { he[sz] = s[i]; val[sz] = val[u]+1; pre[sz] = u; ch[u][c] = Newnode(); } u = ch[u][c]; Have_word[u]++; } //现在的u就是这个单词的最后一个位置 return u; } ll find_word(char *s){ ll u = 0, len = strlen(s); for(ll i = 0; i < len; i++){ ll c = idx(s[i]); if(!ch[u][c])return 0; //节点不存在 u = ch[u][c]; } return Have_word[u]; } void Have_name(char *s, ll now){ ll len = val[now]; s[len--] = 0; ll cc = now; while(cc) { s[len--] = he[cc]; cc = pre[cc]; } } }; Trie ac; char a[1005], b[1005]; int main(){ ll T; while(~scanf("%d",&T)){ while(T--) { cin>>n; init(); ac.init(); while(n--) { cin>>a>>b; ll u, v; u = ac.insert(a); v = ac.insert(b); cout<