GuilinDev

Lc0886

05 August 2008

886 Possible Bipartition

二维数组中每个元素有两个elements，表示互相不喜欢的两个党派，判断是否能完全分开

图的DFS group[i] = 0 means node i hasn’t been visited. group[i] = 1 means node i has been grouped to 1. group[i] = -1 means node i has been grouped to -1.

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

class Solution {
    public boolean possibleBipartition(int N, int[][] dislikes) {
        int[][] graph = new int[N][N];
        for (int[] d : dislikes) {
            graph[d[0] - 1][d[1] - 1] = 1;
            graph[d[1] - 1][d[0] - 1] = 1;
        }
        int[] group = new int[N];
        for (int i = 0; i < N; i++) {
            if (group[i] == 0 && !dfs(graph, group, i, 1)) {
                return false;
            }
        }
        return true;
    }
    private boolean dfs(int[][] graph, int[] group, int index, int g) {
        group[index] = g;
        for (int i = 0; i < graph.length; i++) {
            if (graph[index][i] == 1) {
                if (group[i] == g) {
                    return false;
                }
                if (group[i] == 0 && !dfs(graph, group, i, -g)) {
                    return false;
                }
            }
        }
        return true;
    }
}

图的BFS

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

public boolean possibleBipartition(int n, int[][] dislikes) {
	List<Integer>[] graph = new ArrayList[n];
	for (int i = 0; i < n; i++) {
	  graph[i] = new ArrayList<>();
	}

	for (int[] dislike : dislikes) {
	  int u = dislike[0] - 1;
	  int v = dislike[1] - 1;

	  graph[u].add(v);
	  graph[v].add(u);
	}

	int[] colors = new int[n];

	for (int i = 0; i < n; i++) {
	  if (colors[i] != 0) {
		continue;
	  }

	  colors[i] = 1;

	  Queue<Integer> queue = new LinkedList<>();
	  queue.add(i);

	  while (!queue.isEmpty()) {
		int node = queue.poll();

		for (int adj : graph[node]) {
		  if (colors[adj] == colors[node]) {
			return false;
		  }

		  if (colors[adj] == 0) {
			colors[adj] = -colors[node];
			queue.add(adj);
		  }
		}
	  }
	}

	return true;
  }
  
  // dfs approach
  
public boolean possibleBipartition(int n, int[][] dislikes) {
  List<Integer>[] graph = new ArrayList[n + 1];
  for (int i = 1; i <= n; i++) {
    graph[i] = new ArrayList<>();
  }

  for (int[] dislike : dislikes) {
    graph[dislike[0]].add(dislike[1]);
    graph[dislike[1]].add(dislike[0]);
  }

  int[] colors = new int[n + 1];

  for (int node = 1; node <= n; node++) {
    if (colors[node] == 0 && !paint(colors, node, graph, 1)) {
      return false;
    }
  }

  return true;
}

private boolean paint(int[] colors, int node, List<Integer>[] graph, int color) {
  if (colors[node] != 0) {
    return colors[node] == color;
  }

  colors[node] = color;

  for (int adj : graph[node]) {
    if (!paint(colors, adj, graph, -color)) {
      return false;
    }
  }

  return true;
}

Union Find

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public boolean possibleBipartition(int N, int[][] dislikes) {
        int[] colors = new int[N + 1];
        for(int i = 1; i <= N; ++i) colors[i] = i;
        for(int i = 0; i < dislikes.length; ++i) {
            int p1 = dislikes[i][0], p2 = dislikes[i][1];
            if(colors[p2] == p2) colors[p2] = p1;
            else {
                int[] uf1 = find(p1, colors), uf2 = find(p2, colors);
                if(uf1[0] == uf2[0] && uf1[1] == uf2[1]) return false;
            }
        }
        return true;
    }
    
    private int[] find(int p, int[] colors) {
        int color = 0;
        while(colors[p] != p) {
            p = colors[p];
            color = color == 0 ? 1 : 0;
        }
        return new int[] {p, color};
    }
}
This site is open source. Improve this page.