|
| 1 | +/** |
| 2 | + * Given a set of N people (numbered 1, 2, ..., N), we would like to split |
| 3 | + * everyone into two groups of any size. |
| 4 | + * |
| 5 | + * Each person may dislike some other people, and they should not go into the |
| 6 | + * same group. |
| 7 | + * |
| 8 | + * Formally, if dislikes[i] = [a, b], it means it is not allowed to put the |
| 9 | + * people numbered a and b into the same group. |
| 10 | + * |
| 11 | + * Return true if and only if it is possible to split everyone into two groups |
| 12 | + * in this way. |
| 13 | + * |
| 14 | + * Example 1: |
| 15 | + * Input: N = 4, dislikes = [[1,2],[1,3],[2,4]] |
| 16 | + * Output: true |
| 17 | + * Explanation: group1 [1,4], group2 [2,3] |
| 18 | + * |
| 19 | + * Example 2: |
| 20 | + * Input: N = 3, dislikes = [[1,2],[1,3],[2,3]] |
| 21 | + * Output: false |
| 22 | + * |
| 23 | + * Example 3: |
| 24 | + * Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]] |
| 25 | + * Output: false |
| 26 | + * |
| 27 | + * Note: |
| 28 | + * 1 <= N <= 2000 |
| 29 | + * 0 <= dislikes.length <= 10000 |
| 30 | + * 1 <= dislikes[i][j] <= N |
| 31 | + * dislikes[i][0] < dislikes[i][1] |
| 32 | + * There does not exist i != j for which dislikes[i] == dislikes[j]. |
| 33 | + */ |
| 34 | + |
| 35 | +publicclassPossibleBipartition886 { |
| 36 | +publicbooleanpossibleBipartition(intN,int[][]dislikes) { |
| 37 | +Set<Integer>[]nonGraph =newSet[N+1]; |
| 38 | +for (int[]d:dislikes) { |
| 39 | +if (nonGraph[d[0]] ==null) { |
| 40 | +nonGraph[d[0]] =newHashSet<>(); |
| 41 | + } |
| 42 | +if (nonGraph[d[1]] ==null) { |
| 43 | +nonGraph[d[1]] =newHashSet<>(); |
| 44 | + } |
| 45 | +nonGraph[d[0]].add(d[1]); |
| 46 | +nonGraph[d[1]].add(d[0]); |
| 47 | + } |
| 48 | + |
| 49 | +int[]visited =newint[N+1]; |
| 50 | +for (inti=1;i<=N;i++) { |
| 51 | +if (visited[i] ==0) { |
| 52 | +if (!helper(i,nonGraph,N,visited,1))returnfalse; |
| 53 | + } |
| 54 | + } |
| 55 | +returntrue; |
| 56 | + } |
| 57 | + |
| 58 | +privatebooleanhelper(intcurr,Set<Integer>[]nonGraph,intN,int[]visited,intpre) { |
| 59 | +if (visited[curr] !=0)returnvisited[curr] ==pre; |
| 60 | +visited[curr] =pre; |
| 61 | +if (nonGraph[curr] ==null)returntrue; |
| 62 | +for (intnext:nonGraph[curr]) { |
| 63 | +if (visited[next] ==pre)returnfalse; |
| 64 | +if (visited[next] ==0) { |
| 65 | +if (!helper(next,nonGraph,N,visited, -pre))returnfalse; |
| 66 | + } |
| 67 | + } |
| 68 | +returntrue; |
| 69 | + } |
| 70 | + |
| 71 | + |
| 72 | +/** |
| 73 | + * https://leetcode.com/problems/possible-bipartition/discuss/159085/java-graph |
| 74 | + */ |
| 75 | +publicbooleanpossibleBipartition2(intN,int[][]dislikes) { |
| 76 | +Set<Integer>[]nonGraph =newSet[N+1]; |
| 77 | +for (int[]d:dislikes) { |
| 78 | +if (nonGraph[d[0]] ==null) { |
| 79 | +nonGraph[d[0]] =newHashSet<>(); |
| 80 | + } |
| 81 | +if (nonGraph[d[1]] ==null) { |
| 82 | +nonGraph[d[1]] =newHashSet<>(); |
| 83 | + } |
| 84 | +nonGraph[d[0]].add(d[1]); |
| 85 | +nonGraph[d[1]].add(d[0]); |
| 86 | + } |
| 87 | + |
| 88 | +int[]visited =newint[N+1]; |
| 89 | +for (inti=1;i<=N;i++) { |
| 90 | +if (visited[i] ==0) { |
| 91 | +visited[i] =1; |
| 92 | +Queue<Integer>q =newLinkedList<>(); |
| 93 | +q.add(i); |
| 94 | +while (!q.isEmpty()) { |
| 95 | +intcurr =q.poll(); |
| 96 | +if (nonGraph[curr] ==null)continue; |
| 97 | +for (intnext:nonGraph[curr]) { |
| 98 | +if (visited[next] ==0) { |
| 99 | +visited[next] = -visited[curr]; |
| 100 | +q.add(next); |
| 101 | + }else { |
| 102 | +if (visited[next] ==visited[curr])returnfalse; |
| 103 | + } |
| 104 | + } |
| 105 | + } |
| 106 | + } |
| 107 | + } |
| 108 | +returntrue; |
| 109 | + } |
| 110 | + |
| 111 | +} |