题解：P13915 [PO Final 2024] 鬼抓人 / Tag

# include <bits/stdc++.h>

using namespace std;

string name[200004];
bool is[200004];
int cnt=1;

struct Trie
{
	int id;
	struct Trie* s[27];
};

struct Trie* t;

struct Trie* ini()
{
	struct Trie* tmp = (struct Trie*) malloc (sizeof (struct Trie));
    for(int i = 0; i < 27; i++)
    {
        tmp->s[i] = NULL;
    }	
	tmp->id = -1;
	return tmp;
}

void add(struct Trie* node,string s,int idx)
{	
	
	if (idx >= s.size())
	{
		node->id = cnt++;
		return ;
	}
	int c = s[idx]-'a';
	if (node->s[c] == NULL) node->s[c] = ini();
	add(node->s[c],s,idx+1);
	return ;
}

int getid(struct Trie* node,char s[],int idx)
{
	if (idx >= strlen(s))
	{
		return node->id;
	}
	return getid(node->s[s[idx]-'a'],s,idx+1);
}

int tot;
string ans[200004];
int chk[200004];

int main (void)
{
	int n,m;
	scanf ("%d %d",&n,&m);
	
	t = ini();
	for (int i=1;i<=n;i++)
	{
		cin >> name[i]; 
		add(t,name[i],0);
	}

	is[1] = 1;
	for (int i=1;i<=m;i++)
	{
		char s1[25],s2[25],s3[25];
		scanf ("%s %s %s",s1,s2,s3);
		int i1=getid(t,s1,0);
		int i2=getid(t,s3,0); 
		if (!is[i1] && !chk[i1])
		{
			ans[tot++] = name[i1];
			chk[i1] = 1;
		}
		is[i1]=0; 
		is[i2]=1;
	}

	printf ("%d\n",tot);
	sort(ans,ans+tot); 
	for (int i=0;i<tot;i++)
	{
		cout << ans[i] << ' ';
	}
 	return 0;
}