C++

Forum

 
Improve time efficiency

Pen72 (74)
The code shows terminated due to time out after five cases and also one aborted call case, what can I do to improve? Thanks in advance.

Given an undirect graph, determine if it is bipartite.

Input Format

The first line has two numbers V , E : the number of vertices and the number of edges.

The vertices are numbered in 1,2,...V.

The next E lines describes the edges (u,v). Each line has two numbers u,v : there is an edge connecting vertices u and v.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
 #include <cmath>
#include <cstdio>
#include <vector>
#include <stdbool.h>
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

uint64_t V,e,i,j;
vector<vector<uint64_t> > graph;
vector<uint64_t> color;
vector<bool>vis;
 
bool isBipartite()
{
    color[0] = 1; 
    queue <uint64_t> q;
    q.push(0);
    while (!q.empty())
    {
        uint64_t temp = q.front();
        q.pop();
        for (i=0;i<V;i++)
        {
            if (graph[temp][i] && color[i] == -1) 
            {   color[i] = (uint64_t)(1 - color[temp]);
                q.push(i);
            }
            else if (graph[temp][i] && color[i] == color[temp])
                return 0;                                 
        }
    }
    return 1;
}
 
int main()
{
    uint64_t u,v;
    cin >>V>>e;
    graph.resize(V);
    color.resize(V,-1);
    fill(vis.begin(), vis.end(), 0);
    
    for(i=0;i<V;i++)
        graph[i].resize(V);
    
    for(i=0;i<e;i++)
    {cin>>u>>v;
     u--;v--;
     graph[u][v]=1;
     graph[v][u]=1;
    }
    
    
    if(isBipartite())
        cout<<"YES\n";
    else
        cout<<"NO\n";
    return 0;
}
jonnin (11437)
what to say... you can try to find an algorithm yourself, which is challenging if you don't already know the answer, or you can go to the web and get the algorithm and then code it.

at a glance your algorithm appears to be N*N, while ... for ...
All I will tell you for now is that the algorithm is far better than N*N run time. So the answer is, find a better method.
Topic archived. No new replies allowed.