判断一个连通无向图G是否是二部图

这种算法我做acm时写过无数遍了，给你一个模板吧
算法思路是判断连通图是否有奇环，有就不是二部图，只要在BFS基础上稍作改动就可以了
程序用C写,执行时先输入定点数目，然后输入整个图的邻接矩阵，每行N个数字，一共N行，0或者1,算法时间复杂度O(N^2),N是顶点数目

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

/*
N是图的顶点数
G[1 << 10][1 << 10]代表图的邻接矩阵，G[i][j] = 1,表示i和j连接，否则不连接
q[1 << 10]是BFS使用的队列
dis[1 << 10]是每个顶点到顶点0的最短距离
head表示队头，t是队尾
*/

int G[1 << 10][1 << 10],q[1 << 10],dis[1 << 10],head,h,t,N;

int BIPARTITE()/*在BFS的基础上稍作修改，从顶点编号0开始广搜,是二部图返回1,否则返回0*/
{
int i,j;
memset(dis,-1,sizeof(dis));/*初始化顶点未访问 */
dis[0] = 0;
head = h = t = 0;
while(t <= h)
{
for(i = t;i <= h;i++)
for(j = 0;j < N;j++)
{
if(G[q[i]][j])
{
if(j == q[i]) /*排除自环*/
continue;
if(dis[j] != -1 && (dis[q[i]] - dis[j]) % 2 == 0) /*说明顶点q[i]和顶点j连接会有奇环产生，不是二