-
Notifications
You must be signed in to change notification settings - Fork 99
/
Copy pathBipartite Graph using BFS in C++
47 lines (42 loc) · 1.01 KB
/
Bipartite Graph using BFS in C++
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
Link for the question : https://practice.geeksforgeeks.org/problems/bipartite-graph/1#
Soltion / Code : refer to striver video, for understanding part too !
class Solution {
public:
bool bipartite_bfs(int src, vector<int>adj[], int color[])
{
queue<int>q;
q.push(src);
color[src]=1;
while(!q.empty())
{
int node = q.front();
q.pop();
for(auto it:adj[node])
{
if(color[it]==-1)
{
color[it] = 1-color[node];
q.push(it);
}
else if(color[it]==color[node])
return false;
}
}
return true;
}
public:
bool isBipartite(int V, vector<int>adj[]){
// Code here
int color[V];
memset(color,-1,sizeof color);
for(int i=0;i<V;i++)
{
if(color[i]==-1)
{
if(!bipartite_bfs(i,adj,color))
return false;
}
}
return true;
}
};