Guest User

Untitled

a guest
Aug 17th, 2018
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.21 KB | None | 0 0
  1. /*
  2. * wrote by Alex Vikharev
  3. * 06.11.2010
  4. */
  5.  
  6. import java.io.BufferedReader;
  7. import java.io.BufferedWriter;
  8. import java.io.FileReader;
  9. import java.io.FileWriter;
  10. import java.io.IOException;
  11. import java.util.Arrays;
  12. import java.util.Deque;
  13. import java.util.LinkedList;
  14. import java.util.StringTokenizer;
  15.  
  16. public class Problem21 implements Runnable {
  17.  
  18. private String nextToken() {
  19. if (st == null || !st.hasMoreTokens()) {
  20. try {
  21. st = new StringTokenizer(in.readLine());
  22. } catch (Exception e) {
  23. e.printStackTrace();
  24. return "0";
  25. }
  26. }
  27. return st.nextToken();
  28. }
  29.  
  30. private int nextInt() {
  31. return Integer.parseInt(nextToken());
  32. }
  33.  
  34. private long nextLong() {
  35. return new Long(nextToken());
  36. }
  37.  
  38. private StringTokenizer st;
  39. private BufferedReader in;
  40. private BufferedWriter out;
  41.  
  42. private final static int pow = 'z' - 'a' + 1;
  43.  
  44. private class Automata {
  45. public int statesCount;
  46. public int[][] next;
  47. public boolean[] terminate;
  48.  
  49. public Automata() {
  50. int n = -1;
  51. int m = -1;
  52. int k = -1;
  53.  
  54. n = nextInt();
  55. m = nextInt();
  56. k = nextInt();
  57.  
  58. statesCount = n;
  59.  
  60. next = new int[n][pow];
  61.  
  62. for (int i = 0; i < n; i++) {
  63. Arrays.fill(next[i], -1);
  64. }
  65.  
  66. terminate = new boolean[n];
  67.  
  68. for (int i = 0; i < k; i++) {
  69. int a = nextInt() - 1;
  70. terminate[a] = true;
  71. }
  72.  
  73. for (int i = 0; i < m; i++) {
  74. int a = nextInt() - 1;
  75. int b = nextInt() - 1;
  76. char c = nextToken().charAt(0);
  77. next[a][c - 'a'] = b;
  78. }
  79.  
  80. }
  81. }
  82.  
  83. private void solve() throws IOException {
  84. Automata a1;
  85. Automata a2;
  86. Deque<Integer> d;
  87. int num[];
  88. int rnum[];
  89.  
  90. a1 = new Automata();
  91.  
  92. a2 = new Automata();
  93.  
  94. if (a1.statesCount != a2.statesCount) {
  95. out.write("NO\n");
  96. return;
  97. }
  98.  
  99. num = new int[a1.statesCount];
  100. rnum = new int[a1.statesCount];
  101.  
  102. Arrays.fill(num, -1);
  103. Arrays.fill(rnum, -1);
  104.  
  105. num[0] = 0;
  106. rnum[0] = 0;
  107. d = new LinkedList<Integer>();
  108. d.add(0);
  109.  
  110. while (!d.isEmpty()) {
  111. int a = d.pollFirst();
  112. int b = num[a];
  113. for (int i = 0; i < pow; i++) {
  114. int an = a1.next[a][i];
  115. int bn = a2.next[b][i];
  116. if (an == -1 && bn == -1) {
  117. continue;
  118. }
  119. if ((an == -1 && bn != -1) || (an != -1 && bn == -1)) {
  120. out.write("NO\n");
  121. return;
  122. }
  123. if (num[an] == -1) {
  124. if (rnum[bn] != -1) {
  125. out.write("NO\n");
  126. return;
  127. }
  128. num[an] = bn;
  129. rnum[bn] = an;
  130. d.addLast(an);
  131. } else if (num[an] != bn || rnum[bn] != an) {
  132. out.write("NO\n");
  133. return;
  134. }
  135. }
  136. }
  137. for (int i = 0; i < num.length; i++) {
  138. if (num[i] == -1 || rnum[i] == -1 || a1.terminate[i] != a2.terminate[num[i]]) {
  139. out.write("NO\n");
  140. return;
  141. }
  142. }
  143. out.write("YES\n");
  144.  
  145. }
  146.  
  147. @Override
  148. public void run() {
  149. try {
  150. in = new BufferedReader(new FileReader("isomorphism.in"));
  151. out = new BufferedWriter(new FileWriter("isomorphism.out"));
  152.  
  153. solve();
  154.  
  155. in.close();
  156. out.close();
  157. } catch (Exception e) {
  158. e.printStackTrace();
  159. System.exit(1);
  160. }
  161. }
  162.  
  163. public static void main(String[] args) {
  164. new Thread(new Problem21()).start();
  165. }
  166.  
  167. }
Add Comment
Please, Sign In to add comment