import java.util.*; public class mis { private static int n; private static int m; private static int d; private static final Set<Set<Vertex>> maxCliques = new HashSet<>(); public static void main(String[] args) { final Scanner sc = new Scanner(System.in); n = sc.nextInt(); final Map<Integer, Vertex> vertices = new HashMap<>(); for (int i = 1; i <= n; ++i) { vertices.put(i, new Vertex(i)); } m = sc.nextInt(); d = sc.nextInt(); for (int i = 0; i < m; ++i) { int a = sc.nextInt(); int b = sc.nextInt(); addEdge(vertices, a, b); } BronKerbosch(new HashSet<>(), new HashSet<>(vertices.values()), new HashSet<>()); if (maxCliques.isEmpty()) { System.out.println("NIE"); return; } List<Set<Vertex>> merged = mergeCliques(); Set<Vertex> maxSet = new HashSet<>(); for (Set<Vertex> s : merged) { if (s.size() > maxSet.size()) { maxSet = s; } } List<Integer> ids = new ArrayList<>(); for (Vertex v : maxSet) { ids.add(v.id); } Collections.sort(ids); System.out.println(ids.size()); for (Integer i : ids) { System.out.print(i + " "); } System.out.println(); } private static List<Set<Vertex>> mergeCliques() { boolean change = false; List<Set<Vertex>> current = new ArrayList<>(maxCliques); do { change = false; List<Set<Vertex>> newSet = new ArrayList<>(); for (int i = 0; i < current.size(); ++i) { Set<Vertex> s1 = current.get(i); if (s1.isEmpty()) { continue; } for (int j = i + 1; j < current.size(); ++j) { Set<Vertex> s2 = current.get(j); if (s2.isEmpty()) { continue; } if (!intersect(s1, s2).isEmpty()) { boolean isChange = s1.addAll(s2); s2.clear(); change = change || isChange; } } newSet.add(s1); } current = newSet; } while (change); //for (Set<Vertex> sss : current) { // System.out.println(sss); //} return current; } private static void addEdge(Map<Integer, Vertex> vertices, int i, int j) { final Vertex v = vertices.get(i); final Vertex u = vertices.get(j); v.adj.add(u); u.adj.add(v); } private static void BronKerbosch(Set<Vertex> R, Set<Vertex> P, Set<Vertex> X) { //System.out.println(R + " | " + P + " | " + X); if (P.isEmpty() && X.isEmpty()) { if (R.size() > d) { //System.out.println("LOCAL MAX: " + R); maxCliques.add(new HashSet<>(R)); } } final Set<Vertex> PP = new HashSet<>(P); for (Vertex v : P) { BronKerbosch(addSingle(R, v), intersect(P, v.adj), intersect(X, v.adj)); R.remove(v); PP.remove(v); X.add(v); } } private static Set<Vertex> addSingle(Set<Vertex> set, Vertex vertex) { set.add(vertex); return set; } private static Set<Vertex> intersect(Set<Vertex> set1, Set<Vertex> set2) { final Set<Vertex> result; if (set1.size() > set2.size()) { result = new HashSet<>(set2); result.retainAll(set1); } else { result = new HashSet<>(set1); result.retainAll(set2); } return result; } private static class Vertex { private int id; private Set<Vertex> adj; public Vertex(int id) { this.id = id; this.adj = new HashSet<>(); } @Override public String toString() { return "{" + id + '}'; } } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 | import java.util.*; public class mis { private static int n; private static int m; private static int d; private static final Set<Set<Vertex>> maxCliques = new HashSet<>(); public static void main(String[] args) { final Scanner sc = new Scanner(System.in); n = sc.nextInt(); final Map<Integer, Vertex> vertices = new HashMap<>(); for (int i = 1; i <= n; ++i) { vertices.put(i, new Vertex(i)); } m = sc.nextInt(); d = sc.nextInt(); for (int i = 0; i < m; ++i) { int a = sc.nextInt(); int b = sc.nextInt(); addEdge(vertices, a, b); } BronKerbosch(new HashSet<>(), new HashSet<>(vertices.values()), new HashSet<>()); if (maxCliques.isEmpty()) { System.out.println("NIE"); return; } List<Set<Vertex>> merged = mergeCliques(); Set<Vertex> maxSet = new HashSet<>(); for (Set<Vertex> s : merged) { if (s.size() > maxSet.size()) { maxSet = s; } } List<Integer> ids = new ArrayList<>(); for (Vertex v : maxSet) { ids.add(v.id); } Collections.sort(ids); System.out.println(ids.size()); for (Integer i : ids) { System.out.print(i + " "); } System.out.println(); } private static List<Set<Vertex>> mergeCliques() { boolean change = false; List<Set<Vertex>> current = new ArrayList<>(maxCliques); do { change = false; List<Set<Vertex>> newSet = new ArrayList<>(); for (int i = 0; i < current.size(); ++i) { Set<Vertex> s1 = current.get(i); if (s1.isEmpty()) { continue; } for (int j = i + 1; j < current.size(); ++j) { Set<Vertex> s2 = current.get(j); if (s2.isEmpty()) { continue; } if (!intersect(s1, s2).isEmpty()) { boolean isChange = s1.addAll(s2); s2.clear(); change = change || isChange; } } newSet.add(s1); } current = newSet; } while (change); //for (Set<Vertex> sss : current) { // System.out.println(sss); //} return current; } private static void addEdge(Map<Integer, Vertex> vertices, int i, int j) { final Vertex v = vertices.get(i); final Vertex u = vertices.get(j); v.adj.add(u); u.adj.add(v); } private static void BronKerbosch(Set<Vertex> R, Set<Vertex> P, Set<Vertex> X) { //System.out.println(R + " | " + P + " | " + X); if (P.isEmpty() && X.isEmpty()) { if (R.size() > d) { //System.out.println("LOCAL MAX: " + R); maxCliques.add(new HashSet<>(R)); } } final Set<Vertex> PP = new HashSet<>(P); for (Vertex v : P) { BronKerbosch(addSingle(R, v), intersect(P, v.adj), intersect(X, v.adj)); R.remove(v); PP.remove(v); X.add(v); } } private static Set<Vertex> addSingle(Set<Vertex> set, Vertex vertex) { set.add(vertex); return set; } private static Set<Vertex> intersect(Set<Vertex> set1, Set<Vertex> set2) { final Set<Vertex> result; if (set1.size() > set2.size()) { result = new HashSet<>(set2); result.retainAll(set1); } else { result = new HashSet<>(set1); result.retainAll(set2); } return result; } private static class Vertex { private int id; private Set<Vertex> adj; public Vertex(int id) { this.id = id; this.adj = new HashSet<>(); } @Override public String toString() { return "{" + id + '}'; } } } |