Submission #792884

---

Source Code Expand

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

/**
 * Created by nakajo on 2016/07/02.
 */
public class Main {

    public static MyScanner sc;

    public static void main(String[] args) throws IOException {
        sc = new MyScanner(System.in);
        sc.println(resolve());
        sc.flush();
    }

    public static long resolve() {
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] list = new int[N];
        Mask mask = new Mask(N); // どの数字を使ったか？
        RaceInfo[] infos = new RaceInfo[M];
        for (int i = 0; i < M; i++) {
            infos[i] = new RaceInfo(sc.nextInt(), sc.nextInt());
        }

        List<int[]> permutations = listup(list, 0, N, mask);
        long result = 0;
        for (int[] n : permutations) {
            if (validation(n, infos))
                result++;
        }

        return result;
    }

    public static boolean validation(int[] permutation, RaceInfo[] infos) {
        for (RaceInfo info : infos) {
            if (!info.valid(permutation))
                return false;
        }
        return true;
    }

    public static List<int[]> listup(int[] list, int index, int max, Mask mask) {
        List<int[]> result = new ArrayList<>();
        for (int i = 0; i < max; i++) {
            if (mask.isUsed(i))
                continue;

            list[index] = i;
            mask.record(i);
            if (index < max - 1) {
                result.addAll(listup(Arrays.copyOf(list, list.length), index + 1, max, mask.clone()));
            } else {
                result.add(list);
            }
            mask.revert(i);
        }

        return result;
    }

    public static String dump(int[] list) {
        StringBuilder sb = new StringBuilder();
        for (int n : list) {
            sb.append(n).append(",");
        }
        return sb.toString();
    }

    public static class Mask {
        int[] table;

        public Mask(int N) {
            this.table = new int[N];
        }

        public void reset() {
            table = new int[table.length];
        }

        public boolean isUsed(int num) {
            return this.table[num] == 1;
        }

        public void record(int num) {
            this.table[num] = 1;
        }

        public void revert(int num) {
            this.table[num] = 0;
        }

        public Mask clone() {
            Mask clone = new Mask(this.table.length);
            clone.table = Arrays.copyOf(this.table, this.table.length);
            return clone;
        }
    }

    public static class RaceInfo {
        public int before;
        public int after;

        public RaceInfo(int x, int y) {
            this.before = x - 1;
            this.after = y - 1;
        }

        public boolean valid(int[] list) {
            boolean findAfter = false;
            for (int i = 0; i < list.length; i++) {
                if (list[i] == before) {
                    if (findAfter) return false;
                }
                if (list[i] == after)
                    findAfter = true;
            }
            return true;
        }

        @Override
        public String toString() {
            return String.format("RaceInfo[b:%d, a:%d]", before, after);
        }
    }

    public static class MyScanner extends PrintWriter {
        private final InputStream in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;

        public MyScanner() {
            this(System.in);
        }

        public MyScanner(InputStream source) {
            super(System.out);
            this.in = source;
        }

        private boolean hasNextByte() {
            if (ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (buflen <= 0) {
                    return false;
                }
            }
            return true;
        }

        private int readByte() {
            if (hasNextByte()) return buffer[ptr++];
            else return -1;
        }

        private static boolean isPrintableChar(int c) {
            return 33 <= c && c <= 126;
        }

        private static boolean isNewLine(int c) {
            return c == '\n' || c == '\r';
        }

        public boolean hasNext() {
            while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
            return hasNextByte();
        }

        public boolean hasNextLine() {
            while (hasNextByte() && isNewLine(buffer[ptr])) ptr++;
            return hasNextByte();
        }

        public String next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while (isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public char[] nextCharArray(int len) {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            char[] s = new char[len];
            int i = 0;
            int b = readByte();
            while (isPrintableChar(b)) {
                if (i == len) {
                    throw new InputMismatchException();
                }
                s[i++] = (char) b;
                b = readByte();
            }
            return s;
        }

        public String nextLine() {
            if (!hasNextLine()) {
                throw new NoSuchElementException();
            }
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while (!isNewLine(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public long nextLong() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            long n = 0;
            boolean minus = false;
            int b = readByte();
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            if (b < '0' || '9' < b) {
                throw new NumberFormatException();
            }
            while (true) {
                if ('0' <= b && b <= '9') {
                    n *= 10;
                    n += b - '0';
                } else if (b == -1 || !isPrintableChar(b)) {
                    return minus ? -n : n;
                } else {
                    throw new NumberFormatException();
                }
                b = readByte();
            }
        }

        public int nextInt() {
            long nl = nextLong();
            if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
                throw new NumberFormatException();
            }
            return (int) nl;
        }

        public char nextChar() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            return (char) readByte();
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        public long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++) a[i] = nextLong();
            return a;
        }

        public double[] nextDoubleArray(int n) {
            double[] a = new double[n];
            for (int i = 0; i < n; i++) a[i] = nextDouble();
            return a;
        }

        public void nextIntArrays(int[]... a) {
            for (int i = 0; i < a[0].length; i++) for (int j = 0; j < a.length; j++) a[j][i] = nextInt();
        }

        public int[][] nextIntMatrix(int n, int m) {
            int[][] a = new int[n][];
            for (int i = 0; i < n; i++) a[i] = nextIntArray(m);
            return a;
        }

        public char[][] nextCharMap(int n, int m) {
            char[][] a = new char[n][];
            for (int i = 0; i < n; i++) a[i] = nextCharArray(m);
            return a;
        }

        public void close() {
            super.close();
            try {
                in.close();
            } catch (IOException e) {
            }
        }

        public void debug(Object obj) {
            if (DEBUG) {
                println(obj);
                flush();
            }
        }
    }

    public static boolean DEBUG = false;
}

Submission Info

Judge Result