fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. bool bfs(int s,const vector<vector<int>> &adj,vector<int>&col){
  4. 	int n=adj.size();
  5. 	queue<int> q;
  6. 	q.push(s);
  7. 	col[s]=0;
  8. 	while(!q.empty()){
  9. 		int f=q.front();
  10. 		q.pop();
  11. 		for(int nbg:adj[f]){
  12. 			if(col[nbg]==-1){
  13. 			 	col[nbg]=1-col[f];
  14. 				q.push(nbg);
  15. 			}else{
  16. 				if(col[nbg]==col[f]){
  17. 					return false;
  18. 				}
  19. 			}
  20. 		}
  21. 	}
  22. 	return true;
  23. }
  24. int main(){
  25. 	int v,e;
  26. 	cin>>v>>e;
  27. 	vector<vector<int>> adj(v);
  28. 	for(int i=0;i<e;i++){
  29. 		int u,v;
  30. 		cin>>u>>v;
  31. 		adj[u].push_back(v);
  32. 		adj[v].push_back(u);
  33. 	}
  34.  
  35. 	bool flag=true;
  36. 	vector<int> col(v,-1);
  37. 	for(int i=0;i<v;i++){
  38. 		if(col[i]==-1){
  39. 			if(bfs(i,adj,col)==false){
  40. 				flag=false;
  41. 				break;
  42. 			}
  43. 		}
  44.  
  45. 	}
  46. 	if(flag==true){
  47. 		cout<<"bipartite";
  48. 	}else{
  49. 		cout<<"not bipartite";
  50. 	}
  51. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
5 4

0 1
0 2
1 3
2 4
stdout
copy 
bipartite
https://ideone.com/KazvxJ
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!