fork(5) download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <string>
  4. #include <cstring>
  5.  
  6.  
  7. using namespace std;
  8.  
  9. int visited[130];
  10. int graph[130][130];
  11.  
  12. int dfs(char a, char b)
  13. {
  14. 	if(graph[a][b]==1)
  15. 		return 1;
  16.  
  17. 	visited[a]=1;
  18. 	for(char i='a';i<='z';i++)
  19. 	{
  20. 		if(graph[a][i] && !visited[i])
  21. 		{
  22. 			if(dfs(i,b))
  23. 				return 1;
  24.  
  25. 		}
  26. 	}
  27.  
  28. 	return 0;
  29. }
  30.  
  31. int main(void)
  32. {
  33.  
  34. 	int t;
  35.  
  36. 	scanf("%d",&t);
  37.  
  38. 	while(t--)
  39. 	{
  40.  
  41. 		for(char i='a';i<='z';i++)
  42. 			for(char j='a';j<='z';j++)
  43. 				graph[i][j]=0;
  44.  
  45. 			for(char bb='a';bb<='z';bb++)
  46. 			{
  47. 				graph[bb][bb]=1;
  48. 			}
  49.  
  50. 			for(int i='a';i<='z';i++)
  51. 				visited[i]=0;
  52.  
  53.  
  54. 			char s[1009];
  55. 			char t[1009];
  56. 			scanf("%s",s);
  57. 			scanf("%s",t);
  58. 			int m;
  59. 			scanf("%d",&m);
  60.  
  61. 			if(m==0)
  62. 			{
  63. 				if(strcmp(s,t)==0)
  64. 					printf("YES\n");
  65. 				else
  66. 					printf("NO\n");
  67. 			}
  68.  
  69. 			else
  70. 			{
  71. 				while(m-- > 0)
  72. 				{
  73. 					char a[4];
  74. 					scanf("%s",a);
  75. 					graph[a[0]][a[3]]=1;
  76. 				}
  77.  
  78. 				int len1=strlen(s);
  79. 				int len2= strlen(t);
  80.  
  81. 				if(len1!=len2)
  82. 					printf("NO\n");
  83.  
  84. 				else if(strcmp(s,t)==0)
  85. 					printf("YES\n");
  86.  
  87. 				else
  88. 				{
  89. 					int flg=1;
  90. 					for(int i=0;i<len1;i++)
  91. 					{
  92. 						if(dfs(s[i],t[i])==0)
  93. 						{
  94. 							flg=0;
  95. 							break;
  96. 						}
  97. 						for(char k='a';k<='z';k++)
  98. 							visited[k]=0;
  99. 					}
  100. 					if(flg==1)
  101. 						printf("YES\n");
  102. 					else
  103. 						printf("NO\n");
  104. 				}
  105.  
  106. 			}
  107.  
  108. 		}
  109.  
  110. 		return 0;
  111.  
  112. 	}
Success #stdin #stdout 0s 3364KB
comments (?)
stdin
copy 
3
aa
bb
1
a-&gt;b
ab
ba
2
a-&gt;b
b-&gt;a
a
b
1
b-&gt;a
stdout
copy 
NO
NO
NO
https://ideone.com/qyZW2D
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!