二分圖判定:
   利用廣度優先搜索可以判斷一個圖是否為二分圖。起點s顯然可以隨意定色，每次考慮一條邊(u,v)時顯然u所在集合已定，因此當v為白色時把它放到不包含u的那個集合，而當v為灰色或黑色時(此時v所在集合已經確定)檢查v和u是否在同一個集合。如果是，則該圖不是二分圖，失敗退出。如果是沒有失敗，則算法實際上已經構造出了這兩個集合。在忽略s所在集合的情況下，這個集合的分劃是唯一的（算法步驟中的每一步都是強制的）。

   
 1
 2bool Is_BipartiteGraph(int n,int id[] /* 二分節點集 */ ){
 3    int k,cnt=0;
 4    enum {Gray,Black,White} color[N];
 5    queue<int> _que;
 6    for(int i=0;i<n;i++) color[i]=White;
 7    _que.push(0); color[0]=Black; id[0]=cnt;
 8    while(!_que.empty()){
 9        k=_que.front(); _que.pop();
10        for(int i=0;i<n;i++)
11            if( g[k][i] ){
12                if( Gray == color[i] | Black == color[i] ){    
13                    if( id[i] == id[k] ) return false; 
14                }
15                else{
16                    id[i]=1-id[k];
17                    color[i]=Gray;
18                    _que.push(i);
19                }
20            }
21        color[k]=Black;
22    }
23    return true;
24}


Time_stamp-DFS+邊分類算法：
   把分類規則落實到DFS中，只需在考慮邊(u,v)時檢查v的顏色：
    v是白色，(u,v)是 樹邊 Tree edge
    v是灰色,(u,v)是 后向邊 Back edge
    v是黑色,繼續判定。若find[u]<find[v]說明v是u的后代，因此它是前向邊Forward edge，否則為交叉邊Cross edge。

 1enum{ Tree,Back,Forward,Cross } id[N][N];
 2enum{ Black,White,Gray } color[N]={White};
 3int finish[N],find[N];
 4int time=0;
 5void DFS(int s){
 6    color[s]=Gray; // 開始擴展 
 7    find[s]=++time;
 8    for(int i=0;i<n;i++)
 9        if(g[s][i]){
10            switch (color[i]){
11                case White:{
12                    id[s][i]=Tree;
13                    DFS(i);
14                    break;
15                }
16                case Gray:{
17                    id[s][i]=Back;    
18                    break;
19                }
20                case Black:{
21                    if(find[s]<find[i]) id[s][i]=Forward;
22                    else id[s][i]=Cross;
23                    break;
24                }
25            }
26        }
27    color[s]=Black; //事件結束 
28    finish[s]=++time;
29}