我正在解决一个简单的问题,检查一个图是否是双着色的(二部图)。对于这种使用C++ STL的方法,我使用BFS。正如其他程序员所建议的那样,我已经用cin和cout替换了scanf和printf,但法官仍然报道了TLE。
#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;
}发布于 2015-07-21 20:20:07
停止使用std::list,它是一个双链接列表,不支持快速随机访问。您应该使用std::vector代替,支持O(1)随机访问。
而不是
list<int> *adj;你可以有一个矢量向量,它不仅更快,而且没有内存泄漏。
发布于 2015-07-21 20:32:35
除了其他人所说的,另一个优化是删除这样的操作:
bool *visited = new bool[V];
string *color = new string[1000001];
for(int i=0;i<V;i++)
visited[i] = false;每次调用Graph::BFS函数时都会这样做。不仅每次调用分配程序,您的函数都不会释放内存,从而造成巨大的内存泄漏。
查看您的代码,更好的方法是使用vector并在Graph类本身中移动这些项。
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);
};然后:
#include <algorithm>
//...
void Graph::BFS(int s)
{
visited.resize(V);
color.resize(V);
std::fill(visited.begin(), visited.end(), false);
//...
}这是更优化的,不会泄漏内存。为什么它更理想?您从分配器支付的唯一价格是BFS的第一个呼叫。随后的调用将发出一个resize,但是vector足够聪明,不需要再分配任何内存,因为向量的大小已经达到V的项数。
发布于 2015-07-21 20:35:42
使用std::list代替std::vector,因为std::vector提供快速随机访问(O(1)),但std::list不提供。你可以做的另一件事,尽管我不确定这是否完全相关,不是使用new在构造函数中分配大量内存,而是重写函数,以便在向量向量中使用push_back。
https://codereview.stackexchange.com/questions/97654
复制相似问题