1.undirected graph（無向圖）分兩隊
2.graph二維 每一個節點都可能連很多節點，所以每個節點需要一個 list。
3.cur next
4.二分圖是不是 A、B 沒交集就 true 還不夠 每一條 edge 都必須 A ↔ B，不能 A ↔ A，也不能 B ↔ B
5.group instead of color
6.DFS:cur +1 連的next -1、下一層 +1，一路傳下去
7.0 = 未分組、1 = A 隊、-1 = B 隊。
8.一發現相連兩點同隊，立刻false。但如果沒衝突，因為 Graph 可能不連通，最後還是要檢查所有 component。
9.example
0 —— 1
| |
3 —— 2

graph = {
{1, 3}, // 0 連到 1、3
{0, 2}, // 1 連到 0、2
{1, 3}, // 2 連到 1、3
{0, 2} // 3 連到 0、2
};

所以：graph[cur]就是：目前 cur 連到哪些節點。

class Solution {
public:
    // DFS：讓相連的節點加入相反隊伍
    bool dfs(vector<vector<int>>& graph, vector<int>& group, int cur) {
        for (int next : graph[cur]) {  // 看 cur 連到的每個 next

            if (group[next] == 0) {  // next 還沒分組
                group[next] = -group[cur];  // 加入相反隊伍

                if (!dfs(graph, group, next))  // 繼續往下檢查
                    return false;
            }

            else if (group[next] == group[cur]) {  // 相連兩點竟然同隊
                return false;  // 不是二分圖，提早結束
            }
        }

        return true;  // 這一區沒有衝突
    }

    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();

        vector<int> group(n, 0);  // 0=未分組，1=A，-1=B

        for (int cur = 0; cur < n; ++cur) {  // Graph 可能不連通
            if (group[cur] == 0) {  // 找到新的 component
                group[cur] = 1;  // 隨便先放 A 隊

                if (!dfs(graph, group, cur))
                    return false;
            }
        }

        return true;
    }
};