leetcode

0 class Solution {

1 public:

2 bool possibleBipartition(int n, vector<vector<int>> &dislikes) {

3 vector<vector<int>> adj(n + 1, vector<int>());

4 for (auto &p : dislikes) {

5 adj[p[0]].push_back(p[1]);

6 adj[p[1]].push_back(p[0]);

7 }

8

9 stack<int> st;

10 vector<int> color(n + 1, -1);

11 for (int i = 1; i <= n; i++) {

12 if (color[i] != -1) continue;

13 color[i] = 0;

14 st.push(i);

15 while (!st.empty()) {

16 int root = st.top();

17 st.pop();

18 for (int child : adj[root]) {

19 if (color[child] == color[root]) return false;

20 if (color[child] == -1) {

21 color[child] = !color[root];

22 st.push(child);

23 }

24 }

25 }

26 }

27 return true;

28 }

29 };