首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >使用BFS检查图是否为二分图

问使用BFS检查图是否为二分图
EN

Code Review用户
提问于 2015-07-21 20:16:23
回答 4查看 1.8K关注 0票数 1

我正在解决一个简单的问题,检查一个图是否是双着色的(二部图)。对于这种使用C++ STL的方法,我使用BFS。正如其他程序员所建议的那样,我已经用cin和cout替换了scanf和printf,但法官仍然报道了TLE。

代码语言:javascript
复制
#include<iostream>
#include<list>
#include<cstring>
#include<cstdio>
using namespace std;
int flag = 1;

class Graph
{
    int V;
    list<int> *adj;

    public:
        Graph(int V);
        void addEdge(int v, int w);
        void BFS(int s);
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[1000001];
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w);
    adj[w].push_back(v);
}

void Graph::BFS(int s)
{
    bool *visited = new bool[V];
    string *color = new string[1000001];
    for(int i=0;i<V;i++)
        visited[i] = false;
    list<int> queue;
    queue.push_back(s);
    visited[s] = true;
    color[s] = "red";
    list<int>::iterator i;
    flag = 1;
    while(!queue.empty())
    {
        s = queue.front();
        queue.pop_front();

        for(i = adj[s].begin(); i != adj[s].end(); i++)
        {
            if(!visited[*i])
            {
                visited[*i] = true;
                if(color[s] == "red")
                    color[*i] = "blue";
                if(color[s] == "blue")
                    color[*i] = "red";
                queue.push_back(*i);
            }
            else
            {
                if(color[s] == color[*i])
                    flag = 0;
            }
        }
    }
}


int main()
{
    int T, bugs, edges, from, to;
    scanf("%d", &T);
    int p = T;
    while(T--)
    {
        scanf("%d%d", &bugs, &edges);
        Graph g(bugs+1);
        for(int i=0; i<edges; i++)
        {
            scanf("%d%d", &from, &to);
            g.addEdge(from, to);
        }

        g.BFS(from);

        if(!flag)
            printf("Scenario #%d:\nSuspicious bugs found!\n", p-T);
        else
            printf("Scenario #%d:\nNo suspicious bugs found!\n", p-T);

    }


    return 0;
}
EN

回答 4

Code Review用户

发布于 2015-07-21 20:20:07

停止使用std::list,它是一个双链接列表,不支持快速随机访问。您应该使用std::vector代替,支持O(1)随机访问。

而不是

代码语言:javascript
复制
list<int> *adj;

你可以有一个矢量向量,它不仅更快,而且没有内存泄漏。

票数 3
EN

Code Review用户

发布于 2015-07-21 20:32:35

除了其他人所说的,另一个优化是删除这样的操作:

代码语言:javascript
复制
bool *visited = new bool[V];
string *color = new string[1000001];
for(int i=0;i<V;i++)
    visited[i] = false;

每次调用Graph::BFS函数时都会这样做。不仅每次调用分配程序,您的函数都不会释放内存,从而造成巨大的内存泄漏。

查看您的代码,更好的方法是使用vector并在Graph类本身中移动这些项。

代码语言:javascript
复制
class Graph
{
    int V;
    list<int> *adj;
    std::vector<bool> visited;
    std::vector<std::string> color;

    public:
        Graph(int V);
        void addEdge(int v, int w);
        void BFS(int s);
};

然后:

代码语言:javascript
复制
#include <algorithm>
//...
void Graph::BFS(int s)
{
    visited.resize(V);
    color.resize(V);
    std::fill(visited.begin(), visited.end(), false);
    //...
}

这是更优化的,不会泄漏内存。为什么它更理想?您从分配器支付的唯一价格是BFS的第一个呼叫。随后的调用将发出一个resize,但是vector足够聪明,不需要再分配任何内存,因为向量的大小已经达到V的项数。

票数 2
EN

Code Review用户

发布于 2015-07-21 20:35:42

使用std::list代替std::vector,因为std::vector提供快速随机访问(O(1)),但std::list不提供。你可以做的另一件事,尽管我不确定这是否完全相关,不是使用new在构造函数中分配大量内存,而是重写函数,以便在向量向量中使用push_back。

票数 1
EN
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://codereview.stackexchange.com/questions/97654

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档