`{"id":"1d34045e-0eb6-4013-9ca7-264068889d01","name":"Is Graph Bipartite","description":"1. You are given a graph.\r\n2. You are required to find and print if the graph is bipartite\r\n\r\nNote -> A graph is called bipartite if it is possible to split it's vertices in two sets of mutually \r\n exclusive and exhaustive vertices such that all edges are across sets.","inputFormat":"Input has been managed for you","outputFormat":"true if the graph is bipartite, false otherwise","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\n#include <queue>\n#include<string>\nusing namespace std;\n\nclass Edge\n{\npublic:\n int src = 0;\n int nbr = 0;\n\n Edge(int src, int nbr)\n {\n this->src = src; \n this->nbr = nbr;\n }\n};\n\n\nint main() { \n int vtces;\n cin >> vtces;\n vector<vector<Edge>> graph(vtces, vector<Edge>());\n \n\n int edges;\n cin >> edges;\n\n for (int i = 0; i < edges; i++ ) {\n int u, v, w; \n cin >> u >> v >> w;\n \n graph[u].push_back(Edge(u, v));\n graph[v].push_back(Edge(v, u));\n\n } \n \n // write your code here\n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n static class Edge {\r\n int src;\r\n int nbr;\r\n int wt;\r\n\r\n Edge(int src, int nbr, int wt) {\r\n this.src = src;\r\n this.nbr = nbr;\r\n this.wt = wt;\r\n }\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int vtces = Integer.parseInt(br.readLine());\r\n ArrayList<Edge>[] graph = new ArrayList[vtces];\r\n for (int i = 0; i < vtces; i++) {\r\n graph[i] = new ArrayList<>();\r\n }\r\n\r\n int edges = Integer.parseInt(br.readLine());\r\n for (int i = 0; i < edges; i++) {\r\n String[] parts = br.readLine().split(\" \");\r\n int v1 = Integer.parseInt(parts);\r\n int v2 = Integer.parseInt(parts);\r\n int wt = Integer.parseInt(parts);\r\n graph[v1].add(new Edge(v1, v2, wt));\r\n graph[v2].add(new Edge(v2, v1, wt));\r\n }\r\n\r\n // write your code here\r\n }\r\n}"},"python":{"code":"class Edge:\n def __init__(self,src,nbr):\n self.src = src\n self.nbr = nbr\n\ndef main():\n vtces = int(input())\n edges = int(input())\n graph = {}\n for i in range(vtces):\n graph[i] = []\n \n for i in range(edges):\n lines = input().split(\" \")\n v1=int(lines)\n v2=int(lines)\n e1 = Edge(v1 ,v2 )\n e2 = Edge(v2 ,v1 )\n graph[e1.src].append(e1)\n graph[e2.src].append(e2)\n \n # write your code here\n \nif __name__ == \"__main__\":\n main()"}},"points":10,"difficulty":"easy","sampleInput":"7\r\n8\r\n0 1 10\r\n1 2 10\r\n2 3 10\r\n0 3 10\r\n3 4 10\r\n4 5 10\r\n5 6 10\r\n4 6 10","sampleOutput":"false","questionVideo":"https://www.youtube.com/embed/ZBhZ1DXGrhA?end=375","hints":[],"associated":[{"id":"0689a188-b991-484e-a5e4-c79dd0fd3f8f","name":"If the graph is non cyclic, then the graph will always be Bipartite. Validate the statement? (Is Graph Bipartite)","slug":"if-the-graph-is-non-cyclic-then-the-graph-will-always-be-bipartite-validate-the-statement-is-graph-bipartite","type":4},{"id":"0830e0b8-cc53-4545-a33d-5cc72db72e9d","name":"Which traversal will we use to detect if the graph is bipartite?","slug":"which-traversal-will-we-use-to-detect-if-the-graph-is-bipartite","type":4},{"id":"af0d83cb-8379-4ee4-9c3a-bbb0c9529d38","name":"In which of the following conditions is the graph not bipartite? (Is Graph Bipartite)","slug":"in-which-of-the-following-conditions-is-the-graph-not-bipartite-is-graph-bipartite","type":4},{"id":"d047784c-9395-4f1c-acad-dd0fc47b1532","name":"Which conditions must be true for a graph to be bipartite? (Is Graph Bipartite)","slug":"which-conditions-must-be-true-for-a-graph-to-be-bipartite-is-graph-bipartite","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"02ab8fe3-cddd-43ad-b241-b8b1a2fcd52e","name":"Graphs For Beginners","slug":"graphs-for-beginners","type":0},{"id":"504fe158-a346-4878-a7cc-9aefe2c4051f","name":"Is Graph Bipartite","slug":"is-graph-bipartite","type":1}],"next":{"id":"a23a17fa-e27f-4dfd-ac4e-bdf6c0687482","name":"Is Graph Bipartite","type":3,"slug":"is-graph-bipartite"},"prev":{"id":"e0a724ab-189e-41ba-9c66-c743f0f3ade5","name":"Is Graph Cyclic\"","type":3,"slug":"is-graph-cyclic"}}}`

# Is Graph Bipartite

1. You are given a graph. 2. You are required to find and print if the graph is bipartite Note -> A graph is called bipartite if it is possible to split it's vertices in two sets of mutually exclusive and exhaustive vertices such that all edges are across sets.

`{"id":"1d34045e-0eb6-4013-9ca7-264068889d01","name":"Is Graph Bipartite","description":"1. You are given a graph.\r\n2. You are required to find and print if the graph is bipartite\r\n\r\nNote -> A graph is called bipartite if it is possible to split it's vertices in two sets of mutually \r\n exclusive and exhaustive vertices such that all edges are across sets.","inputFormat":"Input has been managed for you","outputFormat":"true if the graph is bipartite, false otherwise","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\n#include <queue>\n#include<string>\nusing namespace std;\n\nclass Edge\n{\npublic:\n int src = 0;\n int nbr = 0;\n\n Edge(int src, int nbr)\n {\n this->src = src; \n this->nbr = nbr;\n }\n};\n\n\nint main() { \n int vtces;\n cin >> vtces;\n vector<vector<Edge>> graph(vtces, vector<Edge>());\n \n\n int edges;\n cin >> edges;\n\n for (int i = 0; i < edges; i++ ) {\n int u, v, w; \n cin >> u >> v >> w;\n \n graph[u].push_back(Edge(u, v));\n graph[v].push_back(Edge(v, u));\n\n } \n \n // write your code here\n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n static class Edge {\r\n int src;\r\n int nbr;\r\n int wt;\r\n\r\n Edge(int src, int nbr, int wt) {\r\n this.src = src;\r\n this.nbr = nbr;\r\n this.wt = wt;\r\n }\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int vtces = Integer.parseInt(br.readLine());\r\n ArrayList<Edge>[] graph = new ArrayList[vtces];\r\n for (int i = 0; i < vtces; i++) {\r\n graph[i] = new ArrayList<>();\r\n }\r\n\r\n int edges = Integer.parseInt(br.readLine());\r\n for (int i = 0; i < edges; i++) {\r\n String[] parts = br.readLine().split(\" \");\r\n int v1 = Integer.parseInt(parts);\r\n int v2 = Integer.parseInt(parts);\r\n int wt = Integer.parseInt(parts);\r\n graph[v1].add(new Edge(v1, v2, wt));\r\n graph[v2].add(new Edge(v2, v1, wt));\r\n }\r\n\r\n // write your code here\r\n }\r\n}"},"python":{"code":"class Edge:\n def __init__(self,src,nbr):\n self.src = src\n self.nbr = nbr\n\ndef main():\n vtces = int(input())\n edges = int(input())\n graph = {}\n for i in range(vtces):\n graph[i] = []\n \n for i in range(edges):\n lines = input().split(\" \")\n v1=int(lines)\n v2=int(lines)\n e1 = Edge(v1 ,v2 )\n e2 = Edge(v2 ,v1 )\n graph[e1.src].append(e1)\n graph[e2.src].append(e2)\n \n # write your code here\n \nif __name__ == \"__main__\":\n main()"}},"points":10,"difficulty":"easy","sampleInput":"7\r\n8\r\n0 1 10\r\n1 2 10\r\n2 3 10\r\n0 3 10\r\n3 4 10\r\n4 5 10\r\n5 6 10\r\n4 6 10","sampleOutput":"false","questionVideo":"https://www.youtube.com/embed/ZBhZ1DXGrhA?end=375","hints":[],"associated":[{"id":"0689a188-b991-484e-a5e4-c79dd0fd3f8f","name":"If the graph is non cyclic, then the graph will always be Bipartite. Validate the statement? (Is Graph Bipartite)","slug":"if-the-graph-is-non-cyclic-then-the-graph-will-always-be-bipartite-validate-the-statement-is-graph-bipartite","type":4},{"id":"0830e0b8-cc53-4545-a33d-5cc72db72e9d","name":"Which traversal will we use to detect if the graph is bipartite?","slug":"which-traversal-will-we-use-to-detect-if-the-graph-is-bipartite","type":4},{"id":"af0d83cb-8379-4ee4-9c3a-bbb0c9529d38","name":"In which of the following conditions is the graph not bipartite? (Is Graph Bipartite)","slug":"in-which-of-the-following-conditions-is-the-graph-not-bipartite-is-graph-bipartite","type":4},{"id":"d047784c-9395-4f1c-acad-dd0fc47b1532","name":"Which conditions must be true for a graph to be bipartite? (Is Graph Bipartite)","slug":"which-conditions-must-be-true-for-a-graph-to-be-bipartite-is-graph-bipartite","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"02ab8fe3-cddd-43ad-b241-b8b1a2fcd52e","name":"Graphs For Beginners","slug":"graphs-for-beginners","type":0},{"id":"504fe158-a346-4878-a7cc-9aefe2c4051f","name":"Is Graph Bipartite","slug":"is-graph-bipartite","type":1}],"next":{"id":"a23a17fa-e27f-4dfd-ac4e-bdf6c0687482","name":"Is Graph Bipartite","type":3,"slug":"is-graph-bipartite"},"prev":{"id":"e0a724ab-189e-41ba-9c66-c743f0f3ade5","name":"Is Graph Cyclic\"","type":3,"slug":"is-graph-cyclic"}}}` Editor

# Is Graph Bipartite

easy

1. You are given a graph. 2. You are required to find and print if the graph is bipartite Note -> A graph is called bipartite if it is possible to split it's vertices in two sets of mutually exclusive and exhaustive vertices such that all edges are across sets.

None

## Format

### Input

Input has been managed for you

### Output

true if the graph is bipartite, false otherwise

## Example

Sample Input

```.css-23h8hz{color:inherit;font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;}7 8 0 1 10 1 2 10 2 3 10 0 3 10 3 4 10 4 5 10 5 6 10 4 6 10```

### Sample Output

`.css-3oaykw{color:var(--chakra-colors-active-primary);font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;font-family:Monospace;}false`

Question Video

Discussions

Show Discussion

Related Resources 