[785] Is Graph Bipartite?

感覺是一個很老的題目！！！

判斷是不是一個二分圖：在一個無方向graph 裡，如果每一個edge相接的兩個node 分屬不同group，那就是一個二分圖。可以用對node塗色的概念來想！一開始大家都沒有顏色，選一個起始點塗上紅色，和它有edge連接的都塗上綠色。接著往外塗去，如果遇到已經有人上色了的，若是顏色相同，表示這不是一個二分圖。

在一天的亂七八糟之後，終於寫好了！又因為很得意（？）就尾巴翹很高的貼去Leetcode上了！！！這都是因為寫C的人太少了 XD

用一個array存顏色 : 未上色, 顏色A , 顏色B

用另一個array表示我要檢查的node的順序，從node 0 開始，把它的鄰居都丟進去，（所以是dfs吧），丟進去的同時上色，若是已經有顏色的鄰居，就檢查是不是同色，同色return false 。

在for loop裡會優先選擇sequence 裡被insert進來的node去依序做，如果沒有新的node，那就繼續往 i 的下一個未被上色的做。（寫到這裡突然覺得其實是有bug 的吧只是測資沒測出來XD 就如果我insert的都是數字大的node，等到沒有東西進去了，而我的 i 也已經長很大了(?) 那我要怎麼辦XD！！！！！）要再掃一次的意思？！（但我剛剛太得意忘形了我已經貼了怎麼辦XD！）

bool isBipartite(int** graph, int graphSize, int* graphColSize) {

int *color = calloc(graphSize, sizeof(int)*graphSize);

int *sequence = calloc(graphSize, sizeof(int)*graphSize);

int idx = 0;

for (int i=0; i<graphSize;i++)

{

int node=i;

if (sequence[i]!=0)

node = sequence[i];

else if (color[i] == 0)

{

sequence[idx++]= i;

color[i]=1;

}

else

continue;

for (int j=0; j<graphColSize[node];j++)

{

if (color[graph[node][j]]==0)

{

sequence[idx++] = graph[node][j];

color[graph[node][j]] = (color[node]==1)? 2:1;

}

else if (color[graph[node][j]] == color[node])

return false;

}

}

return true;

}