fork download
copy 
  1. #define RED -1																							// First set of vertices
  2. #define BLUE 1																							// Second set of vertices
  3. #define WHITE 0																							// Not processed vertices
  4. #include <queue>
  5. #include <vector>
  6. #include <iostream>
  7. using namespace std;
  8.  
  9. bool isBipartite(vector<int> *listOfVertices, int *colorOfVertices, int sourceVertex, int quantityOfVertex) {
  10. 	bool isBipartite = true;
  11. 	colorOfVertices[sourceVertex] = RED;																//	Color vertex which we started
  12. 	queue <int> orderOfBypassing;																		//	Stores order of bypassing with queue
  13. 	orderOfBypassing.push(sourceVertex);																//  Remember the initial vertex
  14. 	while (!orderOfBypassing.empty()) {																	//	Process until we bypass all connected vertices
  15. 		int currentVertex = orderOfBypassing.front();													//	Remember vertex that came first in queue
  16. 		orderOfBypassing.pop();																			//	Remove it
  17. 		for (auto adjacentVertex : listOfVertices[currentVertex]) {										//	Process all adjacent with current and not processed earlier vertices
  18. 			if (colorOfVertices[adjacentVertex] == WHITE) {
  19. 				colorOfVertices[adjacentVertex] = -colorOfVertices[currentVertex];						//	Color adjacent vertex with inverse color
  20. 				orderOfBypassing.push(adjacentVertex);													//	Add this vertex to the order of bypass
  21. 			}
  22. 			else if (colorOfVertices[adjacentVertex] == colorOfVertices[currentVertex]) {				//	If two adjacent vertices in one set are the same color
  23. 				isBipartite = false;																	//	Graph isn't bipartite
  24. 				break;																					//	We can stop processing
  25. 			}
  26. 		}
  27. 	}
  28. 	return isBipartite;
  29. }
  30.  
  31. int main() {
  32. 	bool answer = true;
  33. 	int quantityOfVertex, quantityOfConnections;
  34. 	cin >> quantityOfVertex >> quantityOfConnections;
  35. 	vector<int> *listOfVertices = new vector<int>[quantityOfVertex];									//	Stores for the each vertex adjacent vertices
  36. 	while (quantityOfConnections--) {																	//	Read all given connections
  37. 		int firstVertex, secondVertex;
  38. 		cin >> firstVertex >> secondVertex;
  39. 		firstVertex--;																					//	We store it numbering from zero, so decrement index of vertices
  40. 		secondVertex--;
  41. 		listOfVertices[firstVertex].push_back(secondVertex);											//	Add vertex to the vector of adjacent vertex
  42. 		listOfVertices[secondVertex].push_back(firstVertex);											//	Do it symmetrically
  43. 	}
  44. 	int *colorOfVertices = new int[quantityOfVertex];													//	For each vertex stores its color
  45. 	for (int indexOfVertex = 0; indexOfVertex < quantityOfVertex; indexOfVertex++) {
  46. 		colorOfVertices[indexOfVertex] = WHITE;															//	Intially, all vetices are white (not processed)
  47. 	}
  48. 	for (int indexOfVertex = 0; indexOfVertex < quantityOfVertex && answer; indexOfVertex++) {			//	Process to the end or until we recognize, that graph isn't bipartite
  49. 		if (colorOfVertices[indexOfVertex] == WHITE) {													//	Process only white vertices
  50. 			answer &= isBipartite(listOfVertices, colorOfVertices, indexOfVertex, quantityOfVertex);	//	Logical conjunction of answers for all graph component 
  51. 		}
  52. 	}
  53. 	cout << (answer ? "YES" : "NO");
  54. 	return 0;
  55. }
Success #stdin #stdout 0s 3420KB
comments (?)
stdin
copy 
12 10
1 3
2 3
4 5
5 6
6 8
6 9
7 9
8 9
8 10
11 12
stdout
copy 
NO
https://ideone.com/r005My
e-olymp 4002!!!!
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!