Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * wrote by Alex Vikharev
- * 06.11.2010
- */
- import java.io.BufferedReader;
- import java.io.BufferedWriter;
- import java.io.FileReader;
- import java.io.FileWriter;
- import java.io.IOException;
- import java.util.Arrays;
- import java.util.Deque;
- import java.util.LinkedList;
- import java.util.StringTokenizer;
- public class Problem21 implements Runnable {
- private String nextToken() {
- if (st == null || !st.hasMoreTokens()) {
- try {
- st = new StringTokenizer(in.readLine());
- } catch (Exception e) {
- e.printStackTrace();
- return "0";
- }
- }
- return st.nextToken();
- }
- private int nextInt() {
- return Integer.parseInt(nextToken());
- }
- private long nextLong() {
- return new Long(nextToken());
- }
- private StringTokenizer st;
- private BufferedReader in;
- private BufferedWriter out;
- private final static int pow = 'z' - 'a' + 1;
- private class Automata {
- public int statesCount;
- public int[][] next;
- public boolean[] terminate;
- public Automata() {
- int n = -1;
- int m = -1;
- int k = -1;
- n = nextInt();
- m = nextInt();
- k = nextInt();
- statesCount = n;
- next = new int[n][pow];
- for (int i = 0; i < n; i++) {
- Arrays.fill(next[i], -1);
- }
- terminate = new boolean[n];
- for (int i = 0; i < k; i++) {
- int a = nextInt() - 1;
- terminate[a] = true;
- }
- for (int i = 0; i < m; i++) {
- int a = nextInt() - 1;
- int b = nextInt() - 1;
- char c = nextToken().charAt(0);
- next[a][c - 'a'] = b;
- }
- }
- }
- private void solve() throws IOException {
- Automata a1;
- Automata a2;
- Deque<Integer> d;
- int num[];
- int rnum[];
- a1 = new Automata();
- a2 = new Automata();
- if (a1.statesCount != a2.statesCount) {
- out.write("NO\n");
- return;
- }
- num = new int[a1.statesCount];
- rnum = new int[a1.statesCount];
- Arrays.fill(num, -1);
- Arrays.fill(rnum, -1);
- num[0] = 0;
- rnum[0] = 0;
- d = new LinkedList<Integer>();
- d.add(0);
- while (!d.isEmpty()) {
- int a = d.pollFirst();
- int b = num[a];
- for (int i = 0; i < pow; i++) {
- int an = a1.next[a][i];
- int bn = a2.next[b][i];
- if (an == -1 && bn == -1) {
- continue;
- }
- if ((an == -1 && bn != -1) || (an != -1 && bn == -1)) {
- out.write("NO\n");
- return;
- }
- if (num[an] == -1) {
- if (rnum[bn] != -1) {
- out.write("NO\n");
- return;
- }
- num[an] = bn;
- rnum[bn] = an;
- d.addLast(an);
- } else if (num[an] != bn || rnum[bn] != an) {
- out.write("NO\n");
- return;
- }
- }
- }
- for (int i = 0; i < num.length; i++) {
- if (num[i] == -1 || rnum[i] == -1 || a1.terminate[i] != a2.terminate[num[i]]) {
- out.write("NO\n");
- return;
- }
- }
- out.write("YES\n");
- }
- @Override
- public void run() {
- try {
- in = new BufferedReader(new FileReader("isomorphism.in"));
- out = new BufferedWriter(new FileWriter("isomorphism.out"));
- solve();
- in.close();
- out.close();
- } catch (Exception e) {
- e.printStackTrace();
- System.exit(1);
- }
- }
- public static void main(String[] args) {
- new Thread(new Problem21()).start();
- }
- }
Add Comment
Please, Sign In to add comment