C++ Programming Code Examples
C++ > Computer Graphics Code Examples
Program to Check if a Given Graph is Bipartite
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/* Program to Check if a Given Graph is Bipartite
The problem takes a graph as input and checks whether it is Bipartite or not.
Bipartite Graph is a graph in which the set of vertices can be divided into two sets such that all vertex should be present in either set 1 or set 2 but not both, and there should no edge between vertices belonging to same set.
cpp-program-perform-greedy-coloring
Set 1 = { 1, 3} and Set 2 = {2,4}, and hence the given graph is bipartite.
cpp-program-check-bipartite-graph
The above graph is not bipartite, as it does not fit the definition.
- Use BFS to traverse all the vertices.
- Take a vertex and colour it red. ('R')
- Colour all its neighbour vertices as ('B'). (Blue = 'B' and Red = 'R')
- Colour the next level vertices as ('R') and so, untill all vertices are coloured.
- If at any step, we encounter contradicting colours, then the given graph to us is not bipartite!.
- Hence, break and print "No" else print "Yes"; */
#include<bits/stdc++.h>
using namespace std;
int n,e,i,j;
vector<vector<int> > graph;
vector<int> color;
bool vis[100011];
bool isBipartite()
{
color[0] = 1; // Mark colour as 1 for first vertex.
queue <int> q;
q.push(0);
while (!q.empty())
{
int temp = q.front();
q.pop();
for (i=0;i<n;i++)
{
if (graph[temp][i] && color[i] == -1) //if there is an edge, and colour is not assigned
{
color[i] = 1 - color[temp];
q.push(i);
}
else if (graph[temp][i] && color[i] == color[temp]) // if there is an edge and both vertices have same colours
return 0; // graph is not bipartite
}
}
return 1;
}
int main()
{
int x,y;
cout<<"Enter number of vertices and edges respectively:";
cin>>n>>e;
cout<<"\n";
graph.resize(n);
color.resize(n,-1);
memset(vis,0,sizeof(vis));
for(i=0;i<n;i++)
graph[i].resize(n);
for(i=0;i<e;i++)
{
cout<<"\nEnter edge vertices of edge "<<i+1<<" :";
cin>>x>>y;
x--; y--;
graph[x][y]=1;
graph[y][x]=1;
}
if(isBipartite())
cout<<"Yes, The given graph is Bipartite.\n";
else
cout<<"No, The given graoh is not Bipartite.\n";
return 0;
}
Test whether container is empty. Returns whether the queue is empty: i.e. whether its size is zero. This member function effectively calls member empty of the underlying container object. Sometimes before actually starting the work with the individual elements of the containers, it is more feasible to look up if the container is empty, so this function finds its usage in such cases. queue::empty() is an inbuilt function in C++ STL which is declared in header file. queue::empty() is used to check whether the associated queue container is empty or not. This function returns either true or false, if the queue is empty (size is 0) then the function returns true, else if the queue is having some value then it will return false.
Check whether eofbit is set. Returns true if the eofbit error state flag is set for the stream. This flag is set by all standard input operations when the End-of-File is reached in the sequence associated with the stream. Note that the value returned by this function depends on the last operation performed on the stream (and not on the next). Operations that attempt to read at the End-of-File fail, and thus both the eofbit and the failbit end up set. This function can be used to check whether the failure is due to reaching the End-of-File or to some other reason.
The cout is a predefined object of ostream class. It is connected with the standard output device, which is usually a display screen. The cout is used in conjunction with stream insertion operator (<<) to display the output on a console. On most program environments, the standard output by default is the screen, and the C++ stream object defined to access it is cout. The "c" in cout refers to "character" and "out" means "output". Hence cout means "character output". The cout object is used along with the insertion operator << in order to display a stream of characters.
Remove next element. Removes the next element in the queue, effectively reducing its size by one. The element removed is the "oldest" element in the queue whose value can be retrieved by calling member queue::front. This calls the removed element's destructor. This member function effectively calls the member function pop_front of the underlying container object. C++ Queue pop() function is used for removing the topmost element of the queue. The function is implied only for deletion of elements.
The sizeof() is an operator that evaluates the size of data type, constants, variable. It is a compile-time operator as it returns the size of any variable or a constant at the compilation time. The size, which is calculated by the sizeof() operator, is the amount of RAM occupied in the computer. The sizeof is a keyword, but it is a compile-time operator that determines the size, in bytes, of a variable or data type. The sizeof operator can be used to get the size of classes, structures, unions and any other user defined data type. The data_type can be the data type of the data, variables, constants, unions, structures, or any other user-defined data type.
FIFO queue. queues are a type of container adaptor, specifically designed to operate in a FIFO context (first-in first-out), where elements are inserted into one end of the container and extracted from the other. queues are implemented as containers adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are pushed into the "back" of the specific container and popped from its "front". The underlying container may be one of the standard container class template or some other specifically designed container class. This underlying container shall support at least the following operations:
The cin object is used to accept input from the standard input device i.e. keyboard. It is defined in the iostream header file. C++ cin statement is the instance of the class istream and is used to read input from the standard input device which is usually a keyboard. The extraction operator(>>) is used along with the object cin for reading inputs. The extraction operator extracts the data from the object cin which is entered using the keyboard. The "c" in cin refers to "character" and "in" means "input". Hence cin means "character input". The cin object is used along with the extraction operator >> in order to receive a stream of characters.
A program shall contain a global function named main, which is the designated start of the program in hosted environment. main() function is the entry point of any C++ program. It is the point at which execution of program is started. When a C++ program is executed, the execution control goes directly to the main() function. Every C++ program have a main() function.
Change size. Resizes the container so that it contains n elements. The vector is a very useful class of C++ for creating the dynamic array. The size of the vector can be changed at any time to solve any programming problem. Many built-in functions exist in C++ for doing the different types of tasks in a vector container. The resize() function is one of them. It is used to change the size of the vector. The vector size can be increased or decreased by using this function. This function does not return any value. If a reallocation happens, the storage is allocated using the container's allocator, which may throw exceptions on failure (for the default allocator, bad_alloc is thrown if the allocation request does not succeed).
Fill block of memory. Sets the first num bytes of the block of memory pointed by ptr to the specified value (interpreted as an unsigned char). This function converts the value of a character to unsigned character and copies it into each of first num character of the object pointed by the given str[]. If the num is larger than string size, it will be undefined.
In computer programming, we use the if statement to run a block code only when a certain condition is met. An if statement can be followed by an optional else statement, which executes when the boolean expression is false. There are three forms of if...else statements in C++: • if statement, • if...else statement, • if...else if...else statement, The if statement evaluates the condition inside the parentheses ( ). If the condition evaluates to true, the code inside the body of if is executed. If the condition evaluates to false, the code inside the body of if is skipped.
In C++, vectors are used to store elements of similar data types. However, unlike arrays, the size of a vector can grow dynamically. That is, we can change the size of the vector during the execution of a program as per our requirements. Vectors are part of the C++ Standard Template Library. To use vectors, we need to include the vector header file in our program. The vector class provides various methods to perform different operations on vectors. Add Elements to a Vector: To add a single element into a vector, we use the push_back() function. It inserts an element into the end of the vector. Access Elements of a Vector: In C++, we use the index number to access the vector elements. Here, we use the at() function to access the element from the specified index.
The if...else statement executes two different codes depending upon whether the test expression is true or false. Sometimes, a choice has to be made from more than 2 possibilities. The if...else ladder allows you to check between multiple test expressions and execute different statements. In C/C++ if-else-if ladder helps user decide from among multiple options. The C/C++ if statements are executed from the top down. As soon as one of the conditions controlling the if is true, the statement associated with that if is executed, and the rest of the C else-if ladder is bypassed. If none of the conditions is true, then the final else statement will be executed.
Inserts a new element at the end of the queue, after its current last element. The content of this new element is initialized to val. This member function effectively calls the member function push_back of the underlying container object. In C++ STL, Queue is a type of container that follows FIFO (First-in-First-Out) elements arrangement i.e. the elements which insert first will be removed first. In queue, elements are inserted at one end known as "back" and are deleted from another end known as "front". In the Data Structure, "push" is an operation to insert an element in any container, "pop" is an operation to remove an element from the container.
In while loop, condition is evaluated first and if it returns true then the statements inside while loop execute, this happens repeatedly until the condition returns false. When condition returns false, the control comes out of loop and jumps to the next statement in the program after while loop. The important point to note when using while loop is that we need to use increment or decrement statement inside while loop so that the loop variable gets changed on each iteration, and at some point condition returns false. This way we can end the execution of while loop otherwise the loop would execute indefinitely. A while loop that never stops is said to be the infinite while loop, when we give the condition in such a way so that it never returns false, then the loops becomes infinite and repeats itself indefinitely.
Access next element. Returns a reference to the next element in the queue. The next element is the "oldest" element in the queue and the same element that is popped out from the queue when queue::pop is called. This member function effectively calls member front of the underlying container object. In C++ STL, Queue is a type of container that follows FIFO (First-in-First-Out) elements arrangement i.e. the elements which insert first will be removed first. In queue, elements are inserted at one end known as "back" and are deleted from another end known as "front". The function front() returns the reference to the first element in the queue i.e. the oldest element in the queue, so it is used to get the first element from the front of the list of a queue.
Logical Operators are used to compare and connect two or more expressions or variables, such that the value of the expression is completely dependent on the original expression or value or variable. We use logical operators to check whether an expression is true or false. If the expression is true, it returns 1 whereas if the expression is false, it returns 0. Assume variable A holds 1 and variable B holds 0:
#include is a way of including a standard or user-defined file in the program and is mostly written at the beginning of any C/C++ program. This directive is read by the preprocessor and orders it to insert the content of a user-defined or system header file into the following program. These files are mainly imported from an outside source into the current program. The process of importing such files that might be system-defined or user-defined is known as File Inclusion. This type of preprocessor directive tells the compiler to include a file in the source code program.
Consider a situation, when we have two persons with the same name, jhon, in the same class. Whenever we need to differentiate them definitely we would have to use some additional information along with their name, like either the area, if they live in different area or their mother's or father's name, etc. Same situation can arise in your C++ applications. For example, you might be writing some code that has a function called xyz() and there is another library available which is also having same function xyz(). Now the compiler has no way of knowing which version of xyz() function you are referring to within your code.
In computer programming, loops are used to repeat a block of code. For example, when you are displaying number from 1 to 100 you may want set the value of a variable to 1 and display it 100 times, increasing its value by 1 on each loop iteration. When you know exactly how many times you want to loop through a block of code, use the for loop instead of a while loop. A for loop is a repetition control structure that allows you to efficiently write a loop that needs to execute a specific number of times.
Access element. Returns a reference to the element at position n in the vector container. A similar member function, vector::at, has the same behavior as this operator function, except that vector::at is bound-checked and signals if the requested position is out of range by throwing an out_of_range exception. Portable programs should never call this function with an argument n that is out of range, since this causes undefined behavior. Function returns the element at the specified position in the vector.
A function is like a black box. It takes in input, does something with it, and then spits out an answer. We have some "terminology" to refer to functions: A function, call it f, and that uses
To find the HCF ('Highest Common Factor') or GCD (Greatest Common Divisor) of 2 or more numbers, make prime factors of the numbers and choose the common prime factors. Then
