data-structures - 检查由几个断开连接的图组成的大图中的二分性？

Question

我在 SPOJ SPOJ:BUGLIFE上做了一个问题 它要求我检查图表是否是二分的。我知道单个连通图的方法，但是对于断开图的组合，我的方法给出了超出时间限制的错误。这是我的方法 - 广度优先搜索，使用循环队列和由邻接列表实现的图形。方法 -> 选择一个源，如果该源顶点=未访问，则假设它是源，则开始广度优先搜索。如果我在 BFS 中发现冲突，那么我会中止整个事情。否则，我会转到另一个未访问的来源。我怎样才能让它更快？或更好？

PS我是图论的新手，所以请详细解释一下。

Answer 1

在非常大的数据集（edages>1000）中进行测试时，以下实现（C++ 版本）足够快。希望能帮助到你。

struct NODE
{
    int color;
    vector<int> neigh_list;
};

bool checkAllNodesVisited(NODE *graph, int numNodes, int & index);

bool checkBigraph(NODE * graph, int numNodes)
{
    int start = 0;

    do 
    {
        queue<int> Myqueue;
        Myqueue.push(start);
        graph[start].color = 0;

        while(!Myqueue.empty())
        {
            int gid = Myqueue.front();
            for(int i=0; i<graph[gid].neigh_list.size(); i++)
            {
                int neighid = graph[gid].neigh_list[i];
                if(graph[neighid].color == -1)
                {
                    graph[neighid].color = (graph[gid].color+1)%2; // assign to another group
                    Myqueue.push(neighid);
                }
                else
                {
                    if(graph[neighid].color == graph[gid].color) // touble pair in the same group
                        return false;
                }
            }
            Myqueue.pop();
        }
    } while (!checkAllNodesVisited(graph, numNodes, start)); // make sure all nodes visited 
                                            // to be able to handle several separated graphs, IMPORTANT!!!

    return true;
}

bool checkAllNodesVisited(NODE *graph, int numNodes, int & index)
{
    for (int i=0; i<numNodes; i++)
    {
        if (graph[i].color == -1)
        {
            index = i;
            return false;
        }
    }

    return true;
}