二分图判定:
   利用广度优先搜索可以判断一个图是否为二分图。起点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}