daily pastebin goal
1%
SHARE
TWEET

Untitled

a guest Aug 17th, 2018 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top