{"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[0]);\r\n int v2 = Integer.parseInt(parts[1]);\r\n int wt = Integer.parseInt(parts[2]);\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[0])\n v2=int(lines[1])\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[0]);\r\n int v2 = Integer.parseInt(parts[1]);\r\n int wt = Integer.parseInt(parts[2]);\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[0])\n v2=int(lines[1])\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"}}}
plane

Editor

Loading...

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.

Constraints

None

Format

Input

Input has been managed for you

Output

true if the graph is bipartite, false otherwise

Example

Sample Input

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

false

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode