其实说实话，在看到这道题时，我并没有想到要用并查集做，我觉得，这道题其实可以暴力。

当然并不是说每输入一个字符串的起始位置就开始暴力更改这个区间，这样肯定是会 T 的。

我所说的暴力呢，是说在每个区间开始的位置标记这个区间是第几个字符串，如果有多个，就取其中最长的一个（因为根据题目要求一定存在符合要求的字符串，所以最长的一定包含了短的），然后最后在输出的时候判断一下该输出哪个字符串就行了。

那么不属于任何一个区间的地方呢？直接输出a不就完了！还有什么小写字母字符串是比全是a的字符串的字典序还要小呢？

注意！在输出过程中，如果遇到这个区间还没输出完，又到了另外一个区间的开始位置时，一定要判断当前正在输出的这个字符串能否将遇到的这个区间的字符串完全包含！如果不能，就立马退出，再输出从这个位置开始的字符串。

思路还是很简单的，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
int n,k,x,m,a[10000001];//a 数组标记每个区间所对应的字符串的下标，这个数组一定要开大一点，否则会 RE
string t[100001];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		cin>>t[i]>>k;
		for(int j=1;j<=k;j++)
		{
			scanf("%d",&x);
			if(t[a[x]].length()<t[i].length())//如果已有区间从 x 开始，则比较两字符串的长度
				a[x]=i;
			m=max(m,x);
		}
	}
	int i=1;
	while(i<=m)
	{
		if(!a[i])//如果当前点不属于任何一个区间，输出'a'
			printf("a");
		else
		{
			int j;
			for(j=0;j<t[a[i]].length();j++)//输出当前区间的字符串
			{
				if(t[a[i+j]].length()+j>t[a[i]].length())//如果遇到另一个区间的开始，且无法完全包含，则退出，因为 a 默认为 0，所以即使不是另一个区间的开始也没有问题
					break;
				else
					printf("%c",t[a[i]][j]);
			}
			i+=j;
			continue;
		}
		i++;
	}
	return 0;
}