Submission #145745

---

Source Code Expand

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Main me = new Main();
        me.execute();
    }

    private int n;
    private int m;
    private int[] relations;

    private void execute() {
        try (Scanner scanner = new Scanner(System.in)) {
            n = scanner.nextInt();
            m = scanner.nextInt();
            relations = new int[n];

            for (int i = 0; i < m; i++) {
                int x = scanner.nextInt();
                int y = scanner.nextInt();
                relations[y - 1] += (1 << x - 1);
            }
        }
        for (int i = 0; i < n; i++) {
            relations[i] = ~relations[i];
        }

        System.out.println(findRelations(0));
    }

    private int findRelations(int relFlg) {
        int topRels = 0;

        for (int i = 0; i < n; i++) {
            if ((relFlg & relations[i]) == 0) {
                int rels = findRelations(relFlg + (1 << i));
                if (topRels < rels) {
                    topRels = rels;
                }
            }
        }

        if (topRels == 0) {
            int flg = 1;
            for (int i = 0; i < n; i++) {
                if (0 < (relFlg & flg)) {
                    topRels++;
                }
                flg <<= 1;
            }
        }
        return topRels;
    }
}

Submission Info

Judge Result