1
class Solution {
2
 public:
3
  bool dfs(vector<int> adj[], vector<int> &color, int node) {
4
    for (auto it : adj[node]) {      // dfs over adjacent nodes
5
      if (color[it] == -1) {         // not visited yet
6
        color[it] = 1 - color[node]; // set different color of adjacent nodes
7
        if (!dfs(adj, color, it)) return false;
8
      } else if (color[it] != 1 - color[node])
9
        return false; // if adjacent nodes have same color
10
    }
11
    return true;
12
  }
13

14
  bool possibleBipartition(int n, vector<vector<int>> &dislikes) {
15
    vector<int> adj[n + 1];
16
    for (int i = 0; i < dislikes.size(); i++) { // undirected graph
17
      adj[dislikes[i][0]].push_back(dislikes[i][1]);
18
      adj[dislikes[i][1]].push_back(dislikes[i][0]);
19
    }
20
    vector<int> color(n + 1, -1); //-1 i.e. not visited yet
21
    for (int i = 1; i <= n; i++) {
22
      if (color[i] == -1) {
23
        color[i] = 0;
24
        if (!dfs(adj, color, i)) return false;
25
      }
26
    }
27
    return true;
28
  }
29
};